search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.

Recent questions tagged theory-of-computation

0 votes
0 answers 8 views
It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?
asked May 29 in Theory of Computation Palash Nandi 1 13 points 8 views
5 votes
3 answers 1.2K views
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$
asked Feb 18 in Theory of Computation Arjun 257 points 1.2K views
3 votes
3 answers 871 views
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)$
asked Feb 18 in Theory of Computation Arjun 257 points 871 views
2 votes
2 answers 738 views
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________
asked Feb 18 in Theory of Computation Arjun 257 points 738 views
2 votes
2 answers 660 views
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}$
asked Feb 18 in Theory of Computation Arjun 257 points 660 views
4 votes
1 answer 837 views
​​​​​​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
asked Feb 18 in Theory of Computation Arjun 257 points 837 views
4 votes
2 answers 764 views
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\} ^* \}$
asked Feb 18 in Theory of Computation Arjun 257 points 764 views
3 votes
1 answer 782 views
​​​​​​​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)^*$
asked Feb 18 in Theory of Computation Arjun 257 points 782 views
1 vote
3 answers 707 views
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$
asked Feb 18 in Theory of Computation Arjun 257 points 707 views
3 votes
1 answer 821 views
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 ^* \}$
asked Feb 18 in Theory of Computation Arjun 257 points 821 views
0 votes
1 answer 435 views
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?$
asked Feb 18 in Theory of Computation Arjun 257 points 435 views
3 votes
5 answers 709 views
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
asked Feb 18 in Theory of Computation Arjun 257 points 709 views
3 votes
2 answers 913 views
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 ___________
asked Feb 18 in Theory of Computation Arjun 257 points 913 views
1 vote
1 answer 50 views
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.
asked Sep 6, 2020 in Theory of Computation iarnav 291 points 50 views
0 votes
0 answers 31 views
0 votes
2 answers 79 views
1 vote
1 answer 168 views
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.
asked Sep 4, 2020 in Theory of Computation Ollie 525 points 168 views
0 votes
2 answers 63 views
What is the difference between reversal and complement of a DFA$?$
asked Sep 4, 2020 in Theory of Computation Kavya sharma 11 points 63 views
0 votes
1 answer 29 views
Does complement of non deterministic CFL can be DCFL? please explain.
asked Sep 4, 2020 in Theory of Computation Akshay sinha 9 points 29 views
1 vote
1 answer 82 views
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?
asked Sep 3, 2020 in Theory of Computation srestha 1k points 82 views
1 vote
2 answers 380 views
$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?
asked Sep 2, 2020 in Theory of Computation suvradip das 125 points 380 views
0 votes
1 answer 28 views
If L is not CFL, it doesnot satisfy pumping lemma- it is false statement But why? If someone give example for it.
asked Sep 2, 2020 in Theory of Computation srestha 1k points 28 views
0 votes
1 answer 51 views
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.
asked Sep 2, 2020 in Theory of Computation srestha 1k points 51 views
0 votes
1 answer 59 views
L={aⁿbⁱ| n<=i<=2n} Is L CFL?
asked Aug 31, 2020 in Theory of Computation suvradip das 125 points 59 views
0 votes
2 answers 156 views
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
asked Aug 27, 2020 in Theory of Computation Ehraz Hasan 366 points 156 views
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.
asked Aug 25, 2020 in Compiler Design abhish1mishra 5 points 42 views
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?
asked Aug 24, 2020 in Theory of Computation jatinsharma437 7 points 43 views
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=?$
asked Aug 23, 2020 in Theory of Computation srestha 1k points 101 views
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?
asked Aug 23, 2020 in Theory of Computation intgate 9 points 103 views
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?
asked Aug 21, 2020 in Theory of Computation xiuhan 13 points 96 views
0 votes
1 answer 54 views
does P=NP ? a)decidable b)undecidable also please explain why it is decidable or undecidable.
asked Aug 19, 2020 in Theory of Computation abhijeet at 9 points 54 views
0 votes
1 answer 79 views
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.
asked Aug 18, 2020 in Theory of Computation abhijeet at 9 points 38 views
0 votes
1 answer 29 views
$S\rightarrow aABc$ $A\rightarrow b$ $B\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 AB$ $A\rightarrow aA|a$ $B\rightarrow bA|b$ Is it regular grammar?
asked Aug 15, 2020 in Theory of Computation srestha 1k points 29 views
0 votes
2 answers 27 views
I recently read that, subset operation is NOT closed under Reg Languages. Can anyone give me one intuitive example of Why So?
asked Aug 15, 2020 in Theory of Computation mamtuj -25 points 27 views
0 votes
1 answer 96 views
0 votes
1 answer 73 views
0 votes
1 answer 42 views
Can anyone tell me the book full name(all 3 if possible) and edition it is? The screenshot is from what to read series version 3.1
asked Aug 2, 2020 in Theory of Computation Sourav Kar 9 points 42 views
0 votes
0 answers 40 views
I need help in understanding the reasoning behind finding total number of states when positions of particular input is fixed from left hand side or right hand side. The Gate Overflow website shows the formula that for: nth position from the left side of the string is ... the number of states is 2n I want to understand the logic behind this generalized formula. How did we come to this conclusion?
asked Aug 1, 2020 in Theory of Computation aryashah2k 2 points 40 views
0 votes
0 answers 45 views
L1={WWʳ |w€(a+b)*} L2= Reversal(L1) What is L1.L2? What is the answer to this question please don't apply closure property I understood through closure property. My doubt is L1.L2 =W.Wʳ.Wʳ.W and this isn't accepted by any pda so shouldn't the answer be not cfl ??
asked Jul 31, 2020 in Theory of Computation Aman kumar jha 5 points 45 views
...