Most answered questions in Theory of Computation

+30 votes

11 answers

1

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 ___________ .

asked Feb 14, 2017 in Theory of Computation by Arjun Veteran (431k points) | 6.3k views

+42 votes

11 answers

2

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\}$

asked Aug 5, 2014 in Theory of Computation by gatecse Boss (17.5k points) | 5.1k views

+27 votes

10 answers

3

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

asked Feb 14, 2018 in Theory of Computation by gatecse Boss (17.5k points) | 5.3k views

+19 votes

9 answers

4

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 \}$

asked Feb 14, 2017 in Theory of Computation by khushtak Loyal (7.1k points) | 2.5k views

+30 votes

9 answers

5

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 ______________ .

asked Feb 14, 2017 in Theory of Computation by Madhav Active (1.6k points) | 4.6k views

+41 votes

9 answers

6

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

asked Sep 16, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 4.3k views

+42 votes

8 answers

7

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 \}$

asked Feb 14, 2017 in Theory of Computation by Arjun Veteran (431k points) | 6.7k views

+32 votes

8 answers

8

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

asked Feb 14, 2017 in Theory of Computation by Arjun Veteran (431k points) | 3.8k views

+16 votes

8 answers

9

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

asked Jul 4, 2016 in Theory of Computation by Anu Loyal (5.8k points) | 4.7k views

+38 votes

8 answers

10

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\}$

asked Feb 12, 2016 in Theory of Computation by Sandeep Singh Loyal (7.2k points) | 5.4k views

+46 votes

8 answers

11

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_____________.

asked Feb 14, 2015 in Theory of Computation by makhdoom ghaya Boss (30.8k points) | 4.5k views

+35 votes

8 answers

12

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$

asked Feb 12, 2015 in Theory of Computation by jothee Veteran (105k points) | 4.9k views

+5 votes

8 answers

13

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

asked Nov 18, 2014 in Theory of Computation by Isha Karn (459 points) | 652 views

+32 votes

8 answers

14

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$

asked Nov 2, 2014 in Theory of Computation by Ishrat Jahan Boss (16.3k points) | 7k views

+40 votes

8 answers

15

GATE2010-41
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$? $n-1$ $n$ $n+1$ $2^{n-1}$

asked Sep 30, 2014 in Theory of Computation by jothee Veteran (105k points) | 5.1k views

+46 votes

8 answers

16

GATE2006-29
If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$'s in $s$ and $n_1(s)$ the number of $1$'s in $s$. Which one of the following languages is not regular? $L=\left \{ s\in (0+1)^* \mid n_{0}(s) \text{ is a 3-digit prime } \right \}$ ... $L=\left \{ s\in (0+1)^*\mid n_{0}(s) \mod 7=n_{1}(s) \mod 5=0 \right \}$

asked Sep 18, 2014 in Theory of Computation by Rucha Shelke Active (3.3k points) | 6.4k views

+25 votes

8 answers

17

GATE1991-17,b
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?

asked Sep 13, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 2.7k views

+5 votes

7 answers

18

ISRO2008-7
Consider the grammar $S \rightarrow ABCc \mid bc$ $BA \rightarrow AB$ $Bb \rightarrow bb$ $Ab \rightarrow ab$ $Aa \rightarrow aa$ Which of the following sentences can be derived by this grammar? abc aab abcc abbc

asked Jun 10, 2016 in Theory of Computation by jothee Veteran (105k points) | 3.3k views

+36 votes

7 answers

19

GATE2016-1-43
Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma = \{X,Z\}$. $Z$ is the initial stack symbol. Let $L$ ... that halts on every input $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic context-free

asked Feb 12, 2016 in Theory of Computation by Sandeep Singh Loyal (7.2k points) | 6k views

+20 votes

7 answers

20

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)^*$

asked Oct 8, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 3.9k views

+23 votes

7 answers

21

GATE1998-1.12
The string $1101$ does not belong to the set represented by $110^*(0 + 1)$ $1(0 + 1)^*101$ $(10)^*(01)^*(00 + 11)^*$ $(00 + (11)^*0)^*$

asked Sep 26, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 4.9k views

+26 votes

7 answers

22

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$.

asked Sep 22, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 3k views

+36 votes

7 answers

23

GATE2009-40
Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^n \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then $L$ is Not recursive Regular Context free but not regular Recursively enumerable but not context free.

asked Sep 22, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 3.3k views

+31 votes

7 answers

24

GATE2009-16, ISRO2017-12
Which one of the following is FALSE? There is a unique minimal DFA for every regular language Every NFA can be converted to an equivalent PDA. Complement of every context-free language is recursive. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

asked Sep 22, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 4.6k views

+29 votes

7 answers

25

GATE2000-2.8
What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states? $L$ must be $\{a^n \mid n \ \text{ is odd}\}$ $L$ must be $\{a^n \mid n \ \text{ is even}\}$ $L$ must be $\{a^n \mid n \geq 0\}$ Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

asked Sep 14, 2014 in Theory of Computation by Kathleen Veteran (52.2k points) | 2.2k views

+1 vote

6 answers

26

MadeEasy Test Series: Theory Of Computation - Identify Class Language
If L1 = { an | n ≥ 0 } and L2 = { bn | n ≥ 0 }, Consider then L1 . L2 wil be a) (ab)^n b) a^n b^n c) b^n a^n d)b^m a^n e) { a^m b^n | m ≥ 0, n ≥ 0 } why answer is d why noy b ????

asked Dec 9, 2017 in Theory of Computation by air1ankit Active (4.7k points) | 217 views

+27 votes

6 answers

27

GATE2017-1-34
If $G$ is a grammar with productions $S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? $abab$ $aaab$ $abbaa$ $babba$

asked Feb 14, 2017 in Theory of Computation by Arjun Veteran (431k points) | 2.5k views

+3 votes

6 answers

28

MadeEasy Subject Test: Theory of Computation - Identify Class Language
Consider the following language, $L= \big\{ xy \mid x, \ y \in \big\{0,1\big\}^{*} \ where \ x \neq y \ but \ |x| = |y| \big\}$ The language is ___________. Regular CFL but not regular CSL but not CFL Recursive but not CSL

asked Jan 9, 2017 in Theory of Computation by Meghashyam Sujay (237 points) | 447 views

+5 votes

6 answers

29

Regular Languages
If L1 contains finite number of strings and L2 is a CFL then $L1\cap L2$ is ____ (A) Regular (B) CSL (C) CFL (D) None of these

asked Nov 27, 2016 in Theory of Computation by Rakesh K Active (1.8k points) | 278 views

+5 votes

6 answers

30

Minimized DFA no of states || Peter Linz
$L = \left \{ a^nb \ ; n\geq 0 \right \} \cup \left \{ b^na \ ; n\geq 1 \right \}$ Minimal DFA for the above language ?

asked Sep 24, 2016 in Theory of Computation by dd Veteran (57.2k points) | 1.1k 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

Most answered questions in Theory of Computation

Recent Posts

Recent Blog Comments