Recent questions and answers in Theory of Computation

+1 vote

1 answer

1

Linear Ambiguous Context Free Grammar
Please post few examples of Linear Ambiguous Context Free Grammar. It would be helpful if you post grammars for famous languages.

answered 3 days ago in Theory of Computation by blackcloud (449 points) | 176 views

+2 votes

2 answers

2

ISRO2020-38
Which of the following is true? Every subset of a regular set is regular Every finite subset of non-regular set is regular The union of two non regular set is not regular Infinite union of finite set is regular

answered 4 days ago in Theory of Computation by smsubham Boss (11.4k points) | 93 views

+1 vote

2 answers

3

ISRO2020-39
The language which is generated by the grammar $S \rightarrow aSa|bSb|a|b$ over the alphabet of $\{a,b\}$ is the set of Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes

answered 5 days ago in Theory of Computation by Ashwani Kumar 2 Boss (16.3k points) | 87 views

+1 vote

1 answer

4

ISRO2020-40
Which of the following classes of languages can validate an IPv4 address in dotted decimal format? It is to be ensured that the decimal values lie between $0$ and $255$. RE and higher CFG and higher CSG and higher Recursively enumerable language

answered 5 days ago in Theory of Computation by Tuhin Dutta Boss (10.5k points) | 131 views

+1 vote

1 answer

5

ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$

answered 5 days ago in Theory of Computation by Tuhin Dutta Boss (10.5k points) | 133 views

+1 vote

1 answer

6

ISRO2020-37
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure

answered 5 days ago in Theory of Computation by `JEET Boss (18.8k points) | 75 views

0 votes

2 answers

7

GO2019-FLT1-46
Which of the following statements is/are not correct? (P) The class of all Turing Machines is countably infinite (Q) The class of all DCFL's is countably infinite (R) The class of all formal languages is uncountably infinite (S) The set of all primes is countably infinite Only R Only R and S All are incorrect except P None of the above

answered Jan 12 in Theory of Computation by blackcloud (449 points) | 257 views

0 votes

1 answer

8

Ullman (TOC) Edition 3 Exercise 9.3 Question 4 (Page No. 400)
We know by Rice's theorem that none of the following problems are decidable. However are they recursively enumerable,or non-RE? Does $L(M)$ contain at least two strings? Is $L(M)$ infinite? Is $L(M)$ a context-free language? Is $L(M) = (L(M))^{R}$?

answered Jan 9 in Theory of Computation by 12345Shivani12345 (15 points) | 17 views

0 votes

2 answers

9

toc#cfg
what is the grammer of this language $^{a^nb^m} /n\neq m$??

answered Jan 9 in Theory of Computation by RAJKISHOR KUMAR (11 points) | 86 views

+55 votes

6 answers

10

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$

answered Jan 8 in Theory of Computation by Nirmal Gaur Active (2.3k points) | 7.3k views

+30 votes

4 answers

11

GATE2016-1-18
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s? $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$ $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$ $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$ $00(0+1)^*11 +11(0+1)^*00$

answered Jan 7 in Theory of Computation by Satbir Boss (23.7k points) | 5.1k views

+3 votes

1 answer

12

GO2019-FLT1-15
Which one of the following statements is not correct? For non-deterministic push down automata (NPDA), set of all languages accepted by empty stack is always a proper subset of set of all languages accepted by final state For deterministic push down ... final state A grammar which generates a DCFL may be ambiguous A deterministic context free grammar (DCFG) can never be ambiguous

answered Jan 7 in Theory of Computation by JashanArora Loyal (6.1k points) | 289 views

0 votes

2 answers

13

Minimal DFA
What will be the number of final and non-final states for the minimal DFA accepting the language which contains all the strings that either begin or end (or both) with 01? Can anyone provide the DFA diagram for this?

answered Jan 6 in Theory of Computation by mahak Sharma (45 points) | 125 views

+62 votes

4 answers

14

GATE2014-2-35
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$ ... $L$ is: decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable

answered Jan 5 in Theory of Computation by swapnilbaviskar10 (55 points) | 10k views

+26 votes

3 answers

15

GATE2014-2-15
If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$ Which one of the following is CORRECT? Only I Only II Both I and II Neither I nor II

answered Jan 5 in Theory of Computation by swapnilbaviskar10 (55 points) | 2.5k views

+34 votes

4 answers

16

GATE2016-1-44
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard many-one ... recursively enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.

answered Jan 2 in Theory of Computation by Kushagra गुप्ता Active (4k points) | 4.8k views

0 votes

2 answers

17

#TOC What will be the minimal DFA of this regular language?
Given L = { 0*1 + 0 + 1* + 10*1} where + symbol is UNION and NOT positive closure. Please draw the Minimal DFA for this.

answered Dec 31, 2019 in Theory of Computation by Spidey_guy (205 points) | 110 views

+1 vote

1 answer

18

NTA NET DEC 2019(Inherently ambiguous language)
Consider the following languages: L1 ={a^nb^nc^m } U {a^nb^mc^m} n, m ≥ 0 L2={wwR|w {a,b}*} Where R represents reversible operation Which one of the following is (are) inherently ambiguous language(s)? 1) Only L1 (2) only L2 3) Both L1 and L2 (4) neither L1 nor L2

answered Dec 31, 2019 in Theory of Computation by Deepakk Poonia (Dee) Boss (27.2k points) | 58 views

0 votes

1 answer

19

NTA NET DEC 2019 (inherently ambiguous)
Consider the following languages: L1 ={a^nb^nc^m } U {a^nb^mc^m} n, m ≥ 0 L2={wwR|w {a,b}*} Where R represents reversible operation Which one of the following is (are) inherently ambiguous language(s)? Only L1 (2) only L2 Both L1 and L2 (4) neither L1 nor L2

answered Dec 31, 2019 in Theory of Computation by Deepakk Poonia (Dee) Boss (27.2k points) | 32 views

+27 votes

5 answers

20

GATE2003-53
A single tape Turing Machine $M$ has two states $q0$ and $q1$, of which $q0$ is the starting state. The tape alphabet of $M$ is $\{0, 1, B\}$ and its input alphabet is $\{0, 1\}$. The symbol $B$ is the blank symbol used to indicate end of an input string. The ... does not halt on any string in $(00+1)^*$ $M$ halts on all strings ending in a $0$ $M$ halts on all strings ending in a $1$

answered Dec 30, 2019 in Theory of Computation by Antaroop (101 points) | 3k views

+1 vote

2 answers

21

Left linear grammar
Consider the following right linear grammar. S->aA/abc A->aA/bB/a B->bB/cC/b C->cC/c Find left linear grammar is equivalent to the above right linear grammar?

answered Dec 30, 2019 in Theory of Computation by Mk Utkarsh Boss (36.4k points) | 262 views

0 votes

1 answer

22

Countable and recursive language relation
Is every countable language recursive enumerable?

answered Dec 28, 2019 in Theory of Computation by smsubham Boss (11.4k points) | 78 views

0 votes

2 answers

23

Michael Sipser Edition 3 Exercise 0 Question 5 (Page No. 26)
If C is a set with c elements, how many elements are in the power set of C? Explain your answer.

answered Dec 26, 2019 in Theory of Computation by smsubham Boss (11.4k points) | 40 views

+2 votes

1 answer

24

regular languages
If L1, L2 be two arbitrary language, Choose incorrect statement(s) (i) If L1.L2 is regular, then L2.L1 is also regular. (ii) L1 = L2 iﬀ L1 \ L2 = ∅ and L2 \ L1 = ∅. (iii) If L ⊆ Σ∗ and L is ﬁnite, then Σ∗ \ L is regular.(\=set difference) (A) Only (i) (B) (i) and (ii) (C) (ii) and (iii) (D) All

answered Dec 26, 2019 in Theory of Computation by blackcloud (449 points) | 231 views

0 votes

1 answer

25

NTA NET DEC 2019 (Chomsky normal form)
Let $\mathrm{G = (V,T,S,P)}$ be any context-free grammar without any $\lambda$-productions or unit productions. Let $\mathrm K$ be the maximum number of symbols on the right of any production in $\mathrm p$. The maximum number of production rules for any equivalent ... $\mathrm{(4) \;K|P|+|T|}$ Where $\mid\mid$ denotes the cardinality of the set.

answered Dec 26, 2019 in Theory of Computation by `JEET Boss (18.8k points) | 45 views

+2 votes

3 answers

26

TOC
Consider the language given below .Find the complement of these language and Explain Complementary language? 1.wwr | w∈(a ,b)* 2.wxwr| x,w∈(a,b)+ 3.ww ∣ w∈(a,b)+ 4.wxw∣ x,w∈(a,b)+

answered Dec 15, 2019 in Theory of Computation by Mayank0343 Junior (505 points) | 604 views

+6 votes

2 answers

27

$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$

answered Dec 13, 2019 in Theory of Computation by Deepakk Poonia (Dee) Boss (27.2k points) | 1.3k views

+3 votes

1 answer

28

Turing Machine Decidability Question
L1= {⟨M⟩| M is a TM and |L(M)| = 5 }. we know about at least and at most case, but someone explain equal to case. Furthermore, I'll complie more questions in same thread only. L2= {⟨M⟩| M is a TM and M does not accept all even numbers}. L3 = {⟨M⟩| M is a TM and M reject all even numbers}.

answered Dec 12, 2019 in Theory of Computation by skyro (11 points) | 428 views

0 votes

3 answers

29

Epsilon Nfa
What would be the |epsilon closure (p)|=?

answered Dec 12, 2019 in Theory of Computation by Praveenk99 (83 points) | 283 views

+11 votes

5 answers

30

No. of states in the minimal finite automata which accepts the binary strings whose equivalent is divisible by 32 is ________?

answered Dec 11, 2019 in Theory of Computation by shivam001 Junior (959 points) | 1.2k views

+40 votes

5 answers

31

GATE2005-IT-38
Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state of the PDA. The stack is initialized with one $Z$ before the start of the operation ... $L(P)$ and $N(P)$ are necessarily $Σ^*$. Neither $L(P)$ nor $N(P)$ are necessarily $Σ^*$

answered Dec 9, 2019 in Theory of Computation by Rushikesh0203 (33 points) | 3.6k views

+41 votes

8 answers

32

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

answered Dec 9, 2019 in Theory of Computation by pritishc Active (1.9k points) | 6.6k views

+16 votes

8 answers

33

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

answered Dec 9, 2019 in Theory of Computation by JashanArora Loyal (6.1k points) | 4.7k views

+27 votes

5 answers

34

GATE2017-1-38
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}|m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}|m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$ I only II only I and II Neither I nor II

answered Dec 8, 2019 in Theory of Computation by jayanth (21 points) | 3.8k views

+17 votes

4 answers

35

ISRO2014-2
The number of states required by a Finite State Machine,to simulate the behavior of a computer with a memory capable of storing 'm' words, each of length 'n' bits is? $m \times 2^n$ $2^{m+n}$ $2^{mn}$ $m+n$

answered Dec 8, 2019 in Theory of Computation by JashanArora Loyal (6.1k points) | 5.3k views

+1 vote

2 answers

36

#toc #regular languages #homomorphism
Which of the following are true for all regular languages and all homomorphisms, Justify with examples.

answered Dec 6, 2019 in Theory of Computation by sameer_hack (17 points) | 134 views

+1 vote

4 answers

37

Peter Linz Edition 4 Exercise 3.1 Question 7 (Page No. 76) Exercise 3.3 Question 9 (Page No. 97)

answered Dec 6, 2019 in Theory of Computation by sameer_hack (17 points) | 518 views

+18 votes

3 answers

38

GATE2007-IT-46
The two grammars given below generate a language over the alphabet $\{x, y, z\}$ $G1 : S \rightarrow x \mid z \mid x \ S \mid z \ S \mid y \ B$ $B \rightarrow y \mid z \mid y \ B \mid z \ B$ ... $x$ is followed by at least one $y$ $G1$ : No $y$ appears after any $x$ $G2$ : Every $y$ is followed by at least one $x$

answered Dec 5, 2019 in Theory of Computation by Kushagra गुप्ता Active (4k points) | 1.4k views

0 votes

2 answers

39

finite automata
Find the number of states in minimized DFA that accepts languages over sigma={a,b},where each string has exactly three a’s and two b’s.

answered Dec 3, 2019 in Theory of Computation by Zaman3027 (17 points) | 71 views

+25 votes

8 answers

40

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?

answered Dec 2, 2019 in Theory of Computation by Kushagra गुप्ता Active (4k points) | 2.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

Recent questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments