# Recent questions tagged theory-of-computation

It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states? $L-\{01\}$ $L \cup \{01\}$ $\{0,1\}^* – L$ $L \cdot L$
Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free? $L_1 \cap \overline{L_2} \\$ $\overline{\overline{L_1} \cup \overline{L_2}} \\$ $L_1 \cup (L_2 \cup \overline{L_2}) \\$ $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________
Suppose we want to design a synchronous circuit that processes a string of $0$'s and $1$'s. Given a string, it produces another string by replacing the first $1$ in any subsequence of consecutive $1$'s by a $0$ ... $\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}$
​​​​​​Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
​​​​​​​Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$
1 vote
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
Consider the following language: $L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$ Which one of the following deterministic finite automata accepts $L?$
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... and $L_2$ are decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $(q,Y) \in \delta(p,a,X).$ Consider the ... $\Gamma = \{ \#, A\}$. The number of strings of length $100$ accepted by the above pushdown automaton is ___________
1 vote
From Wiki. M here is PDA. Please explain both these points. Can someone explain what being said about epsilon transitions? Please explain point 3. How to check conflict between epsilon transition.
L =. a^i b^2j | i,j>=1 is regular or not ?
1 vote
The question says whether the following language is CFL or not(I replaced $with &): B = {x&w | w is a substring of x, x$\in$\Sigma ^{*}$, &$\in \Sigma$} As per my understanding, w is a substring of x, and x$\in$\Sigma ^{*}$(given),$ ... $\Sigma ^{+}$} which is regular, and therefore CFL But in the answer it was given that it is not CFL, Please someone explain.
What is the difference between reversal and complement of a DFA$?$
Does complement of non deterministic CFL can be DCFL? please explain.
1 vote
A student want to prove a relation between the “hello” and “world”, where “hello” and “world” are two problems , if the student proves that “hello” is reducible to “world” and “world” is decidable then “hello” is decidable. L={<M> | M is turing machine and $L\left ( M \right )\preceq _{p}\left \{ 0^{p} 1^{2p}| p>0 \right \}$} Which one ofthe following is decidable?
1 vote
$L={\;\{\;a^{(m+n)}b^{(m+k)}c^{(k+n)}}, m,n,k ≥ 0 \;\}$ $L$ is CFL or DCFL? My logic is push all $a’s$ and then pop $m$ $b’s$ and push $k$ $b’s$, so here we need non determinism, so it should be CFL and not DCFL. Can anyone design a DPDA for it?
If L is not CFL, it doesnot satisfy pumping lemma- it is false statement But why? If someone give example for it.
Which of the following is recursive language? A)L={<M>| M is a DFA and L(M) regular language} B)L={<M>| M is a PDA and L(M) regular language} Can I say, CFL is regular or not is undecidable, So, B) will be non-recursive.
L={aⁿbⁱ| n<=i<=2n} Is L CFL?
Consider the following language $L =$ w $x | x is prefix of w, where$w,x\in \left \{ a,b \right \}^{+}$Which of the following is TRUE? A)L is CFL but not DCFL B)L is CSL but not context free C)L is DCFL but not regular D)None Of these 0 votes 2 answers 42 views How to design a DFA for Σ = {0,1} that accepts the set of strings that contains at least two 0's and at most two 1's. 0 votes 2 answers 43 views When can we say that the string of infinite length is there? Or do we even have string of infinite length at all? 1 vote 1 answer 101 views$L_{1}$is recursive language and$L_{2}$is recursively enumerable language. Then what will be$(1)L_{1}\cup L_{2}=?(2)L_{1}\cap L_{2}=?(3)Decidable\cup undecidable=?(2)decidable\cap undecidable=?$0 votes 1 answer 103 views$L = \{xy|x,y\in\Sigma^*, n_a(x) = n_b(y)\}$What is the class of this language? context sensitive context free regular none of the above why is this not CFL? 0 votes 2 answers 96 views Is it necessary for the CFL string lenghts to be in AP if the alphabet is a singleton set? 0 votes 1 answer 54 views does P=NP ? a)decidable b)undecidable also please explain why it is decidable or undecidable. 0 votes 1 answer 79 views which grammars of Chomsky Classification allows (S → ε) in its production rules ? 0 votes 1 answer 38 views L = { w x (w^r)* ∣ w , x ∈ ( a + b ) * } is it regular language? If so, why? The notation W^r means the reverse string of W. 0 votes 1 answer 29 views$S\rightarrow aABcA\rightarrow bB\rightarrow bA|aB$Will it generate regular grammar? As it generate string in form$aba^{*}bbc$, so it generate regular language. But not regular grammar. right?Because it is left linear and right linear both . So, it is Type-2 ... but not type-3 grammar. right? Someone confirm.$S\rightarrow ABA\rightarrow aA|aB\rightarrow bA|b\$ Is it regular grammar?
I recently read that, subset operation is NOT closed under Reg Languages. Can anyone give me one intuitive example of Why So?