Most answered questions in Theory of Computation

51 votes

14 answers

1

GATE2012-12
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$

What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$

asked Aug 5, 2014 in Theory of Computation gatecse 9.3k views

34 votes

11 answers

2

GATE2017-1-22
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .

Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .

asked Feb 14, 2017 in Theory of Computation Arjun 12.2k views

51 votes

11 answers

3

GATE2015-1-52
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.

asked Feb 14, 2015 in Theory of Computation makhdoom ghaya 7.7k views

42 votes

11 answers

4

GATE2015-2-35
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$

Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$

asked Feb 12, 2015 in Theory of Computation jothee 8k views

33 votes

10 answers

5

GATE2018-35
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only

Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only

asked Feb 14, 2018 in Theory of Computation gatecse 9.4k views

51 votes

10 answers

6

GATE2017-2-39
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: $\begin{array}{|c|c|c|c|}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$

Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below: $\begin{array}{|c|c|c|c|}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$ ... $\widehat{\delta}(q_2, aba)$ is $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$

asked Feb 14, 2017 in Theory of Computation Arjun 11.4k views

20 votes

10 answers

7

GATE2017-2-16
Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$

Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$

asked Feb 14, 2017 in Theory of Computation khushtak 7.6k views

35 votes

10 answers

8

GATE2017-2-25
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .

asked Feb 14, 2017 in Theory of Computation Madhav 6.8k views

54 votes

10 answers

9

GATE2010-39
Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$

Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$

asked Sep 30, 2014 in Theory of Computation jothee 10.8k views

45 votes

10 answers

10

GATE2003-14
The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above

The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above

asked Sep 16, 2014 in Theory of Computation Kathleen 8.1k views

44 votes

9 answers

11

GATE2016-1-42
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$

Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m \geq 0 \text{ and } n >0\}$ and $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$

asked Feb 12, 2016 in Theory of Computation Sandeep Singh 11.8k views

24 votes

9 answers

12

GATE1995-1.9 , ISRO2017-13
In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits respectively, which of the following expressions defines an identifier? $(L + D)^+$ $(L.D)^*$ $L(L + D)^*$ $L(L.D)^*$

In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits respectively, which of the following expressions defines an identifier? $(L + D)^+$ $(L.D)^*$ $L(L + D)^*$ $L(L.D)^*$

asked Oct 8, 2014 in Theory of Computation Kathleen 6.3k views

38 votes

9 answers

13

GATE2008-52
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$

Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$

asked Sep 12, 2014 in Theory of Computation Kathleen 6.3k views

38 votes

8 answers

14

GATE2017-1-37
Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ ... $L\left ( G_{1} \right )\cap L(G_{2})$ is Finite Not finite but regular Context-Free but not regular Recursive but not context-free

Consider the context-free grammars over the alphabet $\left \{ a, b, c \right \}$ given below. $S$ and $T$ are non-terminals. $G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon$ $G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon$ The language $L\left ( G_{1} \right )\cap L(G_{2})$ is Finite Not finite but regular Context-Free but not regular Recursive but not context-free

asked Feb 14, 2017 in Theory of Computation Arjun 6.4k views

17 votes

8 answers

15

ISRO2016-38
What is the highest type number that can be assigned to the following grammar? $S\to Aa,A\to Ba,B \to abc$ Type 0 Type 1 Type 2 Type 3

What is the highest type number that can be assigned to the following grammar? $S\to Aa,A\to Ba,B \to abc$ Type 0 Type 1 Type 2 Type 3

asked Jul 4, 2016 in Theory of Computation Anu 8.4k views

5 votes

8 answers

16

Virtual Gate Test Series: Theory Of Computation - Turing Machine
Let $M$ range over Turing machine descriptions, Consider the set $\text{REG = {M | L(M) is a regular set }}$ and let the complement of $REG$ be $Co-REG.$ Which of the following is true? REG is recursively enumerable but Co-REG is not REG is not recursively enumerable but Co-REG is Both are recursively enumerable. None of the above

Let $M$ range over Turing machine descriptions, Consider the set $\text{REG = {M | L(M) is a regular set }}$ and let the complement of $REG$ be $Co-REG.$ Which of the following is true? REG is recursively enumerable but Co-REG is not REG is not recursively enumerable but Co-REG is Both are recursively enumerable. None of the above

asked Nov 18, 2014 in Theory of Computation Isha Karn 1.1k views

37 votes

8 answers

17

GATE2004-IT-40
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where $K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and $Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$. Which one of the following strings is not a member of $L(M)$? $aaa$ $aabab$ $baaba$ $bab$

Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where $K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and $Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$. Which one of the following strings is not a member of $L(M)$? $aaa$ $aabab$ $baaba$ $bab$

asked Nov 2, 2014 in Theory of Computation Ishrat Jahan 10.6k views

31 votes

8 answers

18

GATE2009-41
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.

The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.

asked Sep 22, 2014 in Theory of Computation Kathleen 7.1k views

24 votes

8 answers

19

GATE2009-12, ISRO2016-37
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes

$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes

asked Sep 22, 2014 in Theory of Computation Kathleen 9.2k views

66 votes

8 answers

20

GATE2006-34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$

asked Sep 22, 2014 in Theory of Computation Rucha Shelke 13.7k views

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

Subjects

Network Sites

Most answered questions in Theory of Computation

Log In

Register

Recent Posts

Subjects

Recent Blog Comments

Network Sites

Most answered questions in Theory of Computation