Recent questions and answers in Theory of Computation

0 votes

4 answers

1

Doubt-DFA
what is the grammar generated by the complement of this DFA and what is the type?

answered 11 hours ago in Theory of Computation by BASANT KUMAR Active (2.6k points) | 49 views

+1 vote

2 answers

2

conversion of right linear grammar to DFA
In converting right linear regular grammar to DFA how to determine the final states? Can anyone tell the procedure?

answered 1 day ago in Theory of Computation by Adhish (11 points) | 99 views

0 votes

1 answer

3

Doubt in Automata
If two finite state machines M and N are isomorphic then M can be transformed to N by relabeling (a) the states alone (b) the edges alone (c) both the states and edges (d) none of the above

answered 2 days ago in Theory of Computation by shaktipratap (53 points) | 157 views

0 votes

1 answer

4

Michael Sipser Edition 3 Exercise 2 Question 28 (Page No. 157)
Give unambiguous $CFG's$ for the following languages$.$ $\text{{$w\mid$ in every prefix of $w$ the number of $a’s$ is at least the number of $b’s$}}$ $\text{{$w\mid$ the number of $a’s$ and the number of $b’s$ in $w$ are equal}}$ $\text{{$w\mid$ the number of $a’s$ is at least the number of $b’s$ in $w$}}$

answered 2 days ago in Theory of Computation by aditi19 Active (4k points) | 22 views

0 votes

1 answer

5

Michael Sipser Edition 3 Exercise 2 Question 27 (Page No. 157)
$G$ is a natural-looking grammar for a fragment of a programming language, but $G$ is ambiguous$.$ Show that $G$ is ambiguous$.$ Give a new unambiguous grammar for the same language$.$

answered 3 days ago in Theory of Computation by aditi19 Active (4k points) | 19 views

0 votes

1 answer

6

Michael Sipser Edition 3 Exercise 2 Question 24 (Page No. 157)
Let $E=\{a^{i}b^{j}\mid i\neq j$ $\text{and}$ $2i\neq j\}.$ Show that $E$ is a context-free language$.$

answered 3 days ago in Theory of Computation by aditi19 Active (4k points) | 19 views

0 votes

1 answer

7

Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$

answered 3 days ago in Theory of Computation by aditi19 Active (4k points) | 22 views

+2 votes

1 answer

8

Regular Expression
Here is the DFA and I need to convert it to regular expression. I get two different answers when removing states in different order. i get b(c+ab)*d when I remove B first and then A while I get (bc*a)*bc*d when I eliminate A first. Which one is right?

answered 4 days ago in Theory of Computation by BASANT KUMAR Active (2.6k points) | 126 views

+18 votes

4 answers

9

GATE2006-IT-33
Consider the pushdown automaton (PDA) below which runs over the input alphabet $(a, b, c)$. It has the stack alphabet $\{Z_0, X\}$ where $Z_0$ is the bottom-of-stack marker. The set of states of the PDA is $(s, t, u, f\}$ where $s$ is the start state and $f$ is the final state. The PDA accepts by ... $\{a^lb^mc^n \mid 2l = m + n\}$ $\{a^lb^mc^n \mid m = n\}$

answered 4 days ago in Theory of Computation by manikantsharma (315 points) | 1.4k views

+28 votes

3 answers

10

GATE2013-33
Consider the DFA $A$ given below. Which of the following are FALSE? Complement of $L(A)$ is context-free. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*) $ For the language accepted by $A, A$ is the minimal DFA. $A$ accepts all strings over $\{0, 1\}$ of length at least $2$. 1 and 3 only 2 and 4 only 2 and 3 only 3 and 4 only

answered 5 days ago in Theory of Computation by adarsh_1997 Active (3.4k points) | 3.3k views

+1 vote

1 answer

11

UGCNET-June-2019-II-80
For a statement A language $L \subseteq \Sigma^*$ is recursive if there exists some turing machine $M$. Which of the following conditions is satisfied for any string $\omega$? If $\omega \in L$, then $M$ accepts $\omega$ and $M$ will not halt ... $M$ halts without reaching to acceptable state If $\omega \in L$, then $M$ halts without reaching to an acceptable state

answered 5 days ago in Theory of Computation by anurag sharma (243 points) | 47 views

0 votes

1 answer

12

Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 9 views

0 votes

1 answer

13

Michael Sipser Edition 3 Exercise 2 Question 18 (Page No. 156)
Let $C$ be a context-free language and $R$ be a regular language$.$ Prove that the language $C\cap R$ is context-free. Let $A = \{w\mid w\in \{a, b, c\}^{*}$ $\text{and}$ $w$ $\text{contains equal numbers of}$ $a’s, b’s,$ $\text{and}$ $c’s\}.$ Use $\text{part (a)}$ to show that $A$ is not a CFL$.$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 11 views

0 votes

1 answer

14

Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 20 views

0 votes

1 answer

15

Michael Sipser Edition 3 Exercise 2 Question 13 (Page No. 156)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ $U\rightarrow 0U00\mid\#$ Describe $L(G)$ in English. Prove that $L(G)$ is not regular$.$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 21 views

0 votes

1 answer

16

Michael Sipser Edition 3 Exercise 2 Question 9 (Page No. 155)
Give a context-free grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why or why not$?$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 13 views

0 votes

1 answer

17

Michael Sipser Edition 3 Exercise 2 Question 6 (Page No. 155)
Give context-free grammars generating the following languages. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$ The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$ $\{w\#x\mid w^{R}$ $\text{is a substring of $ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 22 views

0 votes

1 answer

18

Michael Sipser Edition 3 Exercise 2 Question 4 (Page No. 155)
Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1's}}$ $\text{{w| w starts and ends with the same symbol}}$ ... $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 24 views

0 votes

1 answer

19

Michael Sipser Edition 3 Exercise 2 Question 2 (Page No. 154)
Use the languages $A=\{a^{m}b^{n}c^{n}|m,n\geq 0\}$ and $B=\{a^{n}b^{n}c^{m}|m,n\geq 0\}$ together with $\text{Example 2.36}$ to show that the class of context-free languages is not closed under ... $(a)$ and $\text{DeMorgan's law (Theorem 0.20)}$ to show that the class of context-free languages is not closed under complementation.

answered Aug 14 in Theory of Computation by aditi19 Active (4k points) | 42 views

+1 vote

1 answer

20

self doubt
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??

answered Aug 13 in Theory of Computation by vg653 (145 points) | 126 views

0 votes

3 answers

21

Gateforum mock 2

answered Aug 12 in Theory of Computation by Arjun Veteran (416k points) | 78 views

+19 votes

2 answers

22

GATE2002-2.5
The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output outputs the sum of the present and the previous bits of the input outputs $01$ whenever the input sequence contains $11$ outputs $00$ whenever the input sequence contains $10$ none of the above

answered Aug 9 in Theory of Computation by kittuD⭐ (33 points) | 2.1k views

0 votes

1 answer

23

Reducibility Problem
Consider 2 problems X & Y. Now if X is reducible to Y.What does this mean.please explain with an example.

answered Aug 9 in Theory of Computation by vg653 (145 points) | 56 views

0 votes

1 answer

24

Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.

answered Aug 9 in Theory of Computation by vg653 (145 points) | 7 views

+2 votes

3 answers

25

TM Decidablity
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.

answered Aug 7 in Theory of Computation by Arjun Veteran (416k points) | 586 views

+13 votes

3 answers

26

GATE1998-2.6
Which of the following statements is false? Every finite subset of a non-regular set is regular Every subset of a regular set is regular Every finite subset of a regular set is regular The intersection of two regular sets is regular

answered Aug 6 in Theory of Computation by Vish1compl (11 points) | 1.5k views

+2 votes

2 answers

27

Minimum number of states in the DFA
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$ I draw the following DFA The minimum number of states is 4. The answer given is 8. How is it possible? Please explain.

answered Aug 5 in Theory of Computation by Brij gopal Dixit (189 points) | 471 views

0 votes

1 answer

28

Is countability in gate syllabus ?
Is countability in gate syllabus . I am talking about countable finite, countable infinite , uncountable language in TOC

answered Aug 5 in Theory of Computation by Navneet Walde (11 points) | 48 views

+5 votes

5 answers

29

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 Aug 4 in Theory of Computation by shivam001 (271 points) | 3.4k views

0 votes

2 answers

30

SELF DOUBT TOC MOORE TO MEALY CONVERSION
GIVEN A MOOORE MACHINE WITH N STATES THE CORRESPONDING EQUIVALENT MEALY MACHINE HAS MAXIMUM OF N STATES ............ I THINK IT SHOULD BE FALSE BECZ SAYING MAXIMUM N STATES IS WRONG BECZ THERE IS NO CHANGE IN STATES WHILE CONVERTING MOORE TO MEALY.?? BUT IS GIVEN AS TRUE ...PLEASE CHECK??

answered Aug 4 in Theory of Computation by khushi khan (11 points) | 91 views

+2 votes

1 answer

31

UGCNET-June-2019-II-79
Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine $M$? $G$ is a CFG with $L(G)=\phi$ There exist two TMs $M_1$ and $M_2$ such that $L(M) \subseteq \{L(M_1) \cup L(M_2)\} = $ language of all TMs. $M$ is a TM that accepts $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape a and b only a only a, b and c c only

answered Aug 2 in Theory of Computation by chandrikabhuyan8 (67 points) | 35 views

0 votes

1 answer

32

Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a context-free grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$

answered Aug 1 in Theory of Computation by srai1928 (21 points) | 21 views

+37 votes

5 answers

33

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

answered Aug 1 in Theory of Computation by Doraemon (351 points) | 4.2k views

+8 votes

3 answers

34

TIFR2017-B-9
Which of the following regular expressions correctly accepts the set of all $0/1$-strings with an even (poossibly zero) number of $1$s? $(10^*10^*)^*$ $(0^*10^*1)^*$ $0^*1(10^*1)^*10^*$ $0^*1(0^*10^*10^*)^*10^*$ $(0^*10^*1)^*0^*$

answered Jul 31 in Theory of Computation by MRINMOY_HALDER Active (1.7k points) | 407 views

+38 votes

7 answers

35

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

answered Jul 29 in Theory of Computation by Arnabh Gangwar (115 points) | 5.2k views

0 votes

0 answers

36

Ullman (TOC) Edition 3 Exercise 9.5 Question 3 (Page No. 418 - 419)
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial ... Ogden's lemma to force equality in the lengths of certain substrings as in the hint to Exercise $7.2.5(b)$.

asked Jul 26 in Theory of Computation by Lakshman Patel RJIT Boss (45.1k points) | 26 views

0 votes

0 answers

37

Ullman (TOC) Edition 3 Exercise 9.5 Question 2 (Page No. 418)
Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the instance $(A,B)$ of PCP has no ... homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.

asked Jul 26 in Theory of Computation by Lakshman Patel RJIT Boss (45.1k points) | 12 views

0 votes

0 answers

38

Ullman (TOC) Edition 3 Exercise 9.5 Question 1 (Page No. 418)
Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.

asked Jul 26 in Theory of Computation by Lakshman Patel RJIT Boss (45.1k points) | 4 views

+59 votes

5 answers

39

GATE2014-2-36
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ ... the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular

answered Jul 23 in Theory of Computation by King Suleiman Junior (629 points) | 6.9k views

+32 votes

4 answers

40

GATE2012-46
Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed DFA that ...

answered Jul 23 in Theory of Computation by King Suleiman Junior (629 points) | 3k 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