Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Theory of Computation:
Recent questions tagged theory-of-computation
3
votes
1
answer
31
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 15
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$. $\emptyset$ $\{a\}^*$ $\{a\}$ $\{\varepsilon\}$
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$.$\emptyset$$\{a\}^*$$...
GO Classes
434
views
GO Classes
asked
Jan 21
Theory of Computation
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
1-mark
easy
+
–
2
votes
1
answer
32
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 42
Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensures that $L_1 \cap L_2$ ... and $\left.m \geq 0\right\}$ $L_2=\left\{a^k b^{2 k} c^{2 k} \mid k \geq 0\right\}$
Consider the following context-free language: $L_1=\left\{a^m b^n c^n \mid n, m \geq 0\right\}$. Which of the following choices of language $L_2$ is context-free and ensu...
GO Classes
488
views
GO Classes
asked
Jan 21
Theory of Computation
goclasses2024-mockgate-12
goclasses
theory-of-computation
context-free-language
multiple-selects
2-marks
+
–
8
votes
1
answer
33
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true? If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite ... $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite.
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true?If $\text{D}$ accepts some string of length $n$, the...
GO Classes
616
views
GO Classes
asked
Jan 21
Theory of Computation
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
multiple-selects
2-marks
+
–
3
votes
2
answers
34
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 44
Which of the following statements is/are false? Let $\text{A}$ and $\text{B}$ be sets of languages over some fixed alphabet $\Sigma$, with $\text{A} \subseteq \text{B}$. If $\text{A}$ is closed under some operation $\text{P},$ then ... $\mathrm{L} 2$ $\subseteq \mathrm{L} 1$, then $\mathrm{L} 2$ is decidable.)
Which of the following statements is/are false?Let $\text{A}$ and $\text{B}$ be sets of languages over some fixed alphabet $\Sigma$, with $\text{A} \subseteq \text{B}$. I...
GO Classes
521
views
GO Classes
asked
Jan 21
Theory of Computation
goclasses2024-mockgate-12
goclasses
theory-of-computation
identify-class-language
multiple-selects
2-marks
+
–
5
votes
2
answers
35
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 35
Which one of the following context-free grammars is unambiguous? (Note that $a, b, c,(,),+$ are terminals, $S, X, Y$ are nonterminals, and the start symbol in each case is $S.)$ ... $S \rightarrow \epsilon|()|(S)$ $S \rightarrow \epsilon|(S)| S S$ $S \rightarrow \epsilon|(S)| S$
Which one of the following context-free grammars is unambiguous? (Note that $a, b, c,(,),+$ are terminals, $S, X, Y$ are nonterminals, and the start symbol in each case i...
GO Classes
588
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
context-free-grammar
multiple-selects
1-mark
+
–
3
votes
1
answer
36
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 61
Which of the following is/are undecidable? $L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\}$. $\{\langle M\rangle \mid M$ ... $\}$ $L=\{\langle M\rangle \mid M$ is a DFA and $L(M)$ is uncountable $\}$
Which of the following is/are undecidable?$L=\left\{\langle M\rangle \mid M\right.$ is a TM, $\mathrm{L}(M) \neq \emptyset$, and $\left.\mathrm{L}(M) \neq \Sigma^*\right\...
GO Classes
541
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
decidability
multiple-selects
2-marks
+
–
4
votes
2
answers
37
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 62
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful transition is possible for the given symbol. Note that when encountering a $b$ in state ... $\mathrm{abbb}^+\mathrm{c}^+\mathrm{c}$ $a b^* b b(c c)^+$
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful ...
GO Classes
309
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
finite-automata
regular-expression
2-marks
+
–
4
votes
1
answer
38
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 63
This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpreted, in the natural way, as the numbers $1$ and $-1,$ in ... $\text{L}_1$ Only $\text{L}_2$ Both None
This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpr...
GO Classes
522
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
finite-automata
regular-language
2-marks
+
–
4
votes
1
answer
39
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 64
Which of the following statements about Turing machines is false? For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of $L$. For any grammar $G$ ... Turing machine $A$ which can simulate the behaviour of any given Turing machine $B$ on any given finite input.
Which of the following statements about Turing machines is false?For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of...
GO Classes
495
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
turing-machine
multiple-selects
2-marks
+
–
6
votes
1
answer
40
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 65
Consider the following non-deterministic pushdown automaton. The input alphabet is $\{a, b\}$, the stack alphabet is $\{*, a, b\}$, and the initial stack symbol is $*$. Acceptance is by empty stack. We use $x$ as a variable that ranges over ... and $a, a: a a$ and $a, b: a b$. How many strings of length $12$ are accepted by this NPDA?
Consider the following non-deterministic pushdown automaton. The input alphabet is $\{a, b\}$, the stack alphabet is $\{*, a, b\}$, and the initial stack symbol is $*$. A...
GO Classes
665
views
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
numerical-answers
theory-of-computation
pushdown-automata
2-marks
+
–
0
votes
1
answer
41
What is correct approach to solve such questions ?
ENTJ007
77
views
ENTJ007
asked
Jan 12
Theory of Computation
theory-of-computation
regular-language
+
–
1
votes
1
answer
42
Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?
If it’s DCFL then also construct the DPDA ?
vedantk
133
views
vedantk
asked
Jan 10
Theory of Computation
theory-of-computation
context-free-language
dcfl
identify-class-language
pushdown-automata
+
–
0
votes
1
answer
43
#self doubt
a^n ww^r a^n .. (n>=0, w belongs to (a,b)*) Can someone please explain the flow how we will process the language in CFL.
a^n ww^r a^n .. (n>=0, w belongs to (a,b)*)Can someone please explain the flow how we will process the language in CFL.
Dknights
81
views
Dknights
asked
Jan 8
Theory of Computation
theory-of-computation
+
–
0
votes
1
answer
44
ISRO 2024
Consider the context free grammar $G$ for below for the arithmetic expressions: $E \rightarrow E + E | E \times E | \text{id}$ Which of the follosing statements is TRUE: The string $\text{id} + \text{id} \times \text{id}$ has no parse tree according to $G$ The ... tree according to $G$ The string $\text{id} + \text{id} \times \text{id}$ has more than two parse tree according to $G$
Consider the context free grammar $G$ for below for the arithmetic expressions:$E \rightarrow E + E | E \times E | \text{id}$Which of the follosing statements is TRUE:Th...
Ramayya
231
views
Ramayya
asked
Jan 7
Theory of Computation
isro-2024
theory-of-computation
ambiguous-grammar
+
–
0
votes
0
answers
45
ISRO 2024
Consider the context-free grammer $G$ below. There $S$ is the starting non terminal symbol, while $a$ and $b$ are terminal symbols. $S \rightarrow aaSb | T$ $T \rightarrow Tb | a$ Which of the following statments is true about the language $L(G)$ generated by $G$? ... $aaaabb$ does not $aaaabb$ belongs to $L(G)$ but $aabbaabb$ does not $aaabb$ belongs to $L(G)$ but $aaaaabbb$ does not
Consider the context-free grammer $G$ below. There $S$ is the starting non terminal symbol, while $a$ and $b$ are terminal symbols.$S \rightarrow aaSb | T$$T \rightarrow ...
Ramayya
173
views
Ramayya
asked
Jan 7
Theory of Computation
isro-2024
theory-of-computation
grammar
+
–
2
votes
1
answer
46
ISRO 2024
Which f the following statements is FALSE? The intersection of a regular language and a context-free language is context=free The intersection of a regular language and context-free language is regular The union of two context-free languages is context-free The union of two regular languages is regular
Which f the following statements is FALSE?The intersection of a regular language and a context-free language is context=freeThe intersection of a regular language and con...
Ramayya
161
views
Ramayya
asked
Jan 7
Theory of Computation
isro-2024
theory-of-computation
context-free-language
regular-language
+
–
0
votes
0
answers
47
ISRO 2024
which of the following statements is NOT true? If a language is recursive it complement is recursive If a language is recursive its complement is recursively enumerable If a language and its complement are recursively enumerable it is recursive If a language is recursively enumerable its complement is also recursively enumerable
which of the following statements is NOT true?If a language is recursive it complement is recursiveIf a language is recursive its complement is recursively enumerableIf a...
Ramayya
130
views
Ramayya
asked
Jan 7
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
48
Find the number of final states in DFA that recognizes L, where L= {w1a w2:|w1|≥3,|w2|≤5}, ∑={a, b} and w1, w2 ∈ ∑ * ______
Hritik1204
257
views
Hritik1204
asked
Jan 5
Theory of Computation
theory-of-computation
finite-automata
number-of-dfa
minimal-state-automata
+
–
0
votes
1
answer
49
#Applied Course
Please explain this.
Please explain this.
Dknights
100
views
Dknights
asked
Jan 4
Theory of Computation
theory-of-computation
+
–
1
votes
0
answers
50
Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language
L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t ...
amitarp818
222
views
amitarp818
asked
Dec 28, 2023
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
51
Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
raj_uddeshya157
66
views
raj_uddeshya157
asked
Dec 27, 2023
Theory of Computation
theory-of-computation
gate-preparation
dcfl
dpda
npda
context-free-language
+
–
0
votes
2
answers
52
#self doubt
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid
MIN DFA of {w: w contains an even number of 0s and exactly two 1s} MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid
Dknights
159
views
Dknights
asked
Dec 23, 2023
Theory of Computation
theory-of-computation
+
–
0
votes
1
answer
53
Micheal Sipser 3rd Edition, Problem 2.36
Is the following language context free? $L=\left \{ a^ib^j\:|\: i\neq j\:and\:2i\neq j \right \}$
Is the following language context free?$L=\left \{ a^ib^j\:|\: i\neq j\:and\:2i\neq j \right \}$
rexritz
149
views
rexritz
asked
Dec 16, 2023
Theory of Computation
theory-of-computation
context-free-language
+
–
0
votes
1
answer
54
Countable Sets Self Doubt
Is countable sets part of GATE CS 2024 syllabus?
Is countable sets part of GATE CS 2024 syllabus?
prasoon054
164
views
prasoon054
asked
Dec 7, 2023
Theory of Computation
theory-of-computation
countable-uncountable-set
+
–
0
votes
1
answer
55
parsers and dfa construction
Hi, there my question is while constructing DFA for LL(1) or LR(0), or SLR (1). parsing I'm seeing different variants of DFA for the same problem set, and I'm not able to determine which is correct and which is not please help I'm providing a question ... S->dA/aB A->bA/c B->bB/c so first is this second is this which one is correct and why please ex
Hi, there my question is while constructing DFA for LL(1) or LR(0), or SLR (1). parsing I'm seeing different variants of DFA for the same problem set, and I'm not able to...
utkarsh2077
173
views
utkarsh2077
asked
Dec 4, 2023
Compiler Design
theory-of-computation
number-of-dfa
number-of-states
+
–
Page:
« prev
1
2
3
4
5
6
7
...
155
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register