Most answered questions in Theory of Computation

+19 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 (359k points) | 4.3k views

+13 votes

9 answers

2

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 \}$ $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text ... =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 in Theory of Computation by gatecse Boss (18.3k points) | 2.7k views

+20 votes

9 answers

3

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 (2k points) | 3k views

+22 votes

8 answers

4

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$ $G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon$ ... \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 (359k points) | 2.5k views

+12 votes

8 answers

5

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.7k points) | 1.7k views

+19 votes

8 answers

6

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 (19.1k points) | 4.1k views

+32 votes

8 answers

7

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 (59.6k points) | 2.8k views

+13 votes

7 answers

8

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.9k points) | 4k views

+5 votes

7 answers

9

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 (103k points) | 2.5k views

+26 votes

7 answers

10

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$ denote the language accepted by the PDA Which one of the following is TRUE? $L =\{a^nb^n\mid n \geq0 ... 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.8k points) | 4.3k views

+29 votes

7 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$ ,respectively? $\{ a^mb^n \mid m > ... 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.8k points) | 3.5k views

+34 votes

7 answers

12

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 (40.3k points) | 3.1k views

+15 votes

7 answers

13

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 (59.6k points) | 3.1k views

+1 vote

6 answers

14

doubt_theory of computation
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 (3.8k points) | 171 views

+16 votes

6 answers

15

GATE2017-1-34
If $G$ is a grammar with productions $S\rightarrow SaS|aSb|bSa|SS|\in$ 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 (359k points) | 1.8k views

+1 vote

6 answers

16

MadeEasy TestSeries
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 (311 points) | 251 views

+5 votes

6 answers

17

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.9k points) | 221 views

+5 votes

6 answers

18

Minimized DFA no of states || Peter Linz

asked Sep 24, 2016 in Theory of Computation by Debashish Deka Veteran (57.4k points) | 894 views

+2 votes

6 answers

19

which one is correct ?
Consider R1 and R2 are two regular expression then equality of two regular expression compute in A) polynomial time B) Exponential time C) logarithmic Polynomial time D) Constant Time

asked Sep 13, 2015 in Theory of Computation by Ankit Chourasiya Junior (637 points) | 335 views

+1 vote

6 answers

20

L=set of all bit strings with even number of 1's ...Regular Expression will be .

asked Sep 3, 2015 in Theory of Computation by Ravi_1511 Active (1.9k points) | 1.4k views

+25 votes

6 answers

21

GATE2015-2-21
Consider the following statements. The complement of every Turing decidable language is Turing decidable There exists some language which is in NP but is not Turing decidable If L is a language in NP, L is Turing decidable Which of the above statements is/are true? Only II Only III Only I and II Only I and III

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

+23 votes

6 answers

22

GATE2007-IT-72
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which deterministic finite automaton accepts the language represented by the regular expression $R$?

asked Oct 31, 2014 in Theory of Computation by Ishrat Jahan Boss (19.1k points) | 1.2k views

+14 votes

6 answers

23

GATE2007-IT-47
Consider the following DFA in which $S_0$ is the start state and $S_1$, $S_3$ are the final states. What language does this DFA recognize? All strings of $x$ and $y$ All strings of $x$ and $y$ which have either even number of $x$ and even number of $y$ or odd ... strings of $x$ and $y$ with either even number of $x$ and odd number of $y$ or odd number of $x$ and even number of $y$

asked Oct 30, 2014 in Theory of Computation by Ishrat Jahan Boss (19.1k points) | 721 views

+20 votes

6 answers

24

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 (59.6k points) | 2.2k views

+33 votes

6 answers

25

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$

asked Sep 22, 2014 in Theory of Computation by Rucha Shelke Active (3.7k points) | 5.4k views

+35 votes

6 answers

26

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+ ... )-n_{1}(s)\mid \leq 4 \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.7k points) | 3.8k views

+27 votes

6 answers

27

GATE2003-50
Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is $1$ $5$ $7$ $8$

asked Sep 17, 2014 in Theory of Computation by Kathleen Veteran (59.6k points) | 2.5k views

+23 votes

6 answers

28

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 (59.6k points) | 1.4k views

+18 votes

6 answers

29

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 (59.6k points) | 1.9k views

+30 votes

6 answers

30

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 (18.3k points) | 3.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