Recent questions and answers in Theory of Computation - GATE Overflow

+15 votes

3 answers

1

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 10 hours ago in Theory of Computation by Kushagra गुप्ता Active (1.8k points) | 1.3k views

0 votes

2 answers

2

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 2 days ago in Theory of Computation by Zaman3027 (17 points) | 62 views

+23 votes

8 answers

3

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 3 days ago in Theory of Computation by Kushagra गुप्ता Active (1.8k points) | 2.5k views

+9 votes

3 answers

4

GATE2019-34
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$ S2: Set of all syntactically valid C programs S3: Set of all languages over the alphabet $\{0,1\}$ S4: Set of all non-regular languages over the alphabet $\{ 0,1 \}$ Which of the above sets are uncountable? S1 and S2 S3 and S4 S2 and S3 S1 and S4

answered 5 days ago in Theory of Computation by JashanArora Active (1.7k points) | 2.4k views

+10 votes

5 answers

5

GATE2019-15
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$

answered 5 days ago in Theory of Computation by JashanArora Active (1.7k points) | 4.5k views

0 votes

1 answer

6

Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.

answered Nov 26 in Theory of Computation by Kunal ghanghav (23 points) | 34 views

0 votes

4 answers

7

RegulaR Expression
Find the regular expression No 2 a's and 2 b's should come together?

answered Nov 25 in Theory of Computation by tech_beardo (205 points) | 794 views

+39 votes

9 answers

8

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

answered Nov 22 in Theory of Computation by ankitron (257 points) | 4k views

+28 votes

6 answers

9

GATE1997-6.4
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring? $0^*(1+0)^*$ $0^*1010^*$ $0^*1^*01^*$ $0^*(10+1)^*$

answered Nov 19 in Theory of Computation by dhruv1232 (15 points) | 6.5k views

+2 votes

1 answer

10

Testbook Test Series: Theory of Computation - Identify Class Language
Consider the infinite two-dimensional grid G={(m,n)| m and n are integers} Every point in G has 4 neighbors, North, South, East, and West, obtained by varying m or n by 1. Starting at the origin (0,0), a ... the following statements is TRUE? i) L is Regular. ii) L is context free. iii) L complement is context free. Thanks!

answered Nov 17 in Theory of Computation by pritishc Junior (657 points) | 48 views

0 votes

1 answer

11

answered Nov 17 in Theory of Computation by Deepalitrapti Junior (843 points) | 54 views

+2 votes

1 answer

12

Regular language or Not
I have a set of languages. which is needed to be categorized as regular or not regular languages...Here i have mentioned some of them please help me to understand which are regular and which are not regular with the proper explanation... 1: {ww/ w ∈ {a, b }* } 2: {ww/ w ∈ {a, b }+ } 3 ... 8: {ww^R/ w∈ {a, b}+ ,w^R is reverse of w } 9: {ww^R/ w∈ {a, b}* ,w^R is reverse of w }

answered Nov 12 in Theory of Computation by adeemajain (213 points) | 822 views

+3 votes

2 answers

13

TIFR2019-B-10
Let the language $D$ be defined in the binary alphabet $\{0,1\}$ as follows: $D:= \{ w \in \{0,1\}^* \mid \text{ substrings 01 and 10 occur an equal number of times in w} \}$ For example , $101 \in D$ while $1010 \notin D$. Which of the ... ? $D$ is regular $D$ is context-free but not regular $D$ is decidable but not context-free $D$ is decidable but not in NP $D$ is undecidable

answered Nov 11 in Theory of Computation by Doraemon Junior (729 points) | 277 views

0 votes

1 answer

14

geeks mock 2017 #56
Which of the following statements is correct about context sensitive grammar? I) In a context sensitive grammar, ε can't be the right hand side of any production II) In a context sensitive grammar, number of grammar symbols on the left hand side of a production ... of non-terminals on the right hand side Isn't (II) (non contracting grammar is also CSL) and (IV) both are correct

answered Nov 10 in Theory of Computation by JashanArora Active (1.7k points) | 305 views

+1 vote

2 answers

15

#theory of computation # turing machine
Suppose M1 and M2 are two TM’s such that L(M1) = L(M2). Then A On every input on which M1 doesn’t halt, M2 doesn’t halt too. B On every i/p on which M1 halts, M2 halts too. C On every i/p which M1 accepts, M2 halts. D None of above

answered Nov 10 in Theory of Computation by JashanArora Active (1.7k points) | 383 views

0 votes

1 answer

16

Peter Linz Edition 4 Exercise 7.3 Question 4 (Page No. 200)
Is the language $L =$ {$a^nb^n : n ≥ 1$} $∪$ {$a$} deterministic?

answered Nov 6 in Theory of Computation by sakharam Active (3k points) | 26 views

+1 vote

1 answer

17

Peter Linz Edition 4 Exercise 7.3 Question 6 (Page No. 200)
For the language $L =$ {$a^nb^{2n} : n ≥ 0$}, show that $L^*$ is a deterministic context-free language.

answered Nov 6 in Theory of Computation by sakharam Active (3k points) | 12 views

0 votes

1 answer

18

Peter Linz Edition 4 Exercise 7.3 Question 15 (Page No. 200)
Show that every regular language is a deterministic context-free language.

answered Nov 6 in Theory of Computation by sakharam Active (3k points) | 15 views

0 votes

1 answer

19

Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.

answered Nov 6 in Theory of Computation by sakharam Active (3k points) | 14 views

0 votes

1 answer

20

Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).

answered Nov 6 in Theory of Computation by sakharam Active (3k points) | 11 views

0 votes

1 answer

21

Ullman (TOC) Edition 3 Exercise 7.1 Question 1 (Page No. 275)
Find a grammar equivalent to $S\rightarrow AB|CA$ $A\rightarrow a$ $B\rightarrow BC|AB$ $C\rightarrow aB|b$ with no useless symbols.

answered Nov 1 in Theory of Computation by Akash Papnai (465 points) | 25 views

+2 votes

2 answers

22

Turing Machine-Techtud
If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine $A)$ Regular Language $B)$ CFL $C)$ CSL $D)$ None Ans given CSL but I thought it should be regular then what is difference between input restricted and constant size tape? https://gateoverflow.in/26653/gate1991-17-a Plz confirm what is correct?

answered Oct 31 in Theory of Computation by AkashChandraGupta (229 points) | 166 views

0 votes

3 answers

23

turing machine
can we have a turing machine which has only one state ? or the minimum number of state for a turing machine is 2?

answered Oct 31 in Theory of Computation by AkashChandraGupta (229 points) | 79 views

0 votes

2 answers

24

Made Easy Test Series : TOC- Turing Machine
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ is TM that halt on all ... Non-Recursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?

answered Oct 31 in Theory of Computation by AkashChandraGupta (229 points) | 294 views

0 votes

1 answer

25

Turing Machine
...................................

answered Oct 31 in Theory of Computation by AkashChandraGupta (229 points) | 144 views

0 votes

1 answer

26

Ace Test Series 2019: Theory Of Computation - Push Down Automata

answered Oct 30 in Theory of Computation by Deepalitrapti Junior (843 points) | 79 views

+1 vote

2 answers

27

answered Oct 28 in Theory of Computation by Chirag Shilwant (103 points) | 199 views

0 votes

1 answer

28

Homomorphism and Inverse homomorphism
Let L1 = { anb2n | n >= 1}, and h(p) = a , h(q) = aa. If L2 = h-1(L1) . What will be the language? Please explain the operation of homomorphism for understanding. I am unable to follow inverse homomorphism.

answered Oct 26 in Theory of Computation by Yash4444 Junior (731 points) | 348 views

+4 votes

3 answers

29

TOC SAMPLE PRACTICE
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these

answered Oct 22 in Theory of Computation by dhruvil3 (13 points) | 1.1k views

+2 votes

0 answers

30

Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 52 views

+1 vote

0 answers

31

Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 16 views

0 votes

0 answers

32

Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 7 views

0 votes

0 answers

33

Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 10 views

0 votes

0 answers

34

Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you ... decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 15 views

+1 vote

0 answers

35

Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 11 views

0 votes

0 answers

36

Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 6 views

0 votes

0 answers

37

Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 10 views

0 votes

0 answers

38

Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$ ... of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 7 views

0 votes

0 answers

39

Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (54.8k points) | 5 views

+1 vote

1 answer

40

Mod Machine
Can we have a mod- n machine with states less than n? Does it exist for a particular n?

answered Oct 19 in Theory of Computation by Shubhdhiman (11 points) | 109 views

To see more, click for all the questions in this category.

Recent questions and answers in Theory of Computation

50,648 questions

56,422 answers

195,196 comments

99,856 users