Recent questions and answers in Theory of Computation

+1 vote

1 answer

1

Michael Sipser Edition 3 Exercise 1 Question 5 (Page No. 84)
Each of the following languages is the complement of a simpler language. In each part, construct a $\text{DFA}$ for the simpler language, then use it to give the state diagram of a $\text{DFA}$ ... $\text{\{w| w is any string except a and b\}}$

answered 18 hours ago in Theory of Computation by aditi19 Active (2.9k points) | 21 views

0 votes

1 answer

2

Michael Sipser Edition 3 Exercise 1 Question 29 (Page No. 88)
Use the pumping lemma to show that the following languages are not regular. $A_{1}=\{0^{n}1^{n}2^{n}|n\geq 0\}$ $A_{2}=\{www|w\in\{a,b\}^{*}\}$ $A_{3}=\{a^{{2}^{n}}|n\geq 0\}$ $\text{(Here,}$\text{$a^{{2}^{n}}$}$ $\text{means a strings of $2^{n}$ a's.)}$

answered 20 hours ago in Theory of Computation by prashant jha 1 Active (5.1k points) | 13 views

0 votes

0 answers

3

Self-Doubt(P-NP class)
$1)$ If the complement of NP-Complete problem is in NP, then can we also say , for this case complement of NP problem is in NP-Complete ? $2)$ If the complement of NP-Complete problem is in Co-NP, then can we also say, for this case complement of Co-NP problem is in NP-Complete?

asked 1 day ago in Theory of Computation by srestha Veteran (111k points) | 31 views

0 votes

0 answers

4

Michael Sipser Edition 3 Exercise 1 Question 30 (Page No. 88)
Describe the error in the following $ $proof$"$ that $0^{*}1^{*}$ is not a regular language. $($An error must exist because $0^{*}1^{*}$ is regular.$)$ The proof is by contradiction. Assume that $0^{*}1^{*}$ is regular ... example $1.73$ shows that $s$ cannot be pumped. Thus you have a contradiction. So $0^{*}1^{*}$ is not regular.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 17 views

0 votes

0 answers

5

Michael Sipser Edition 3 Exercise 1 Question 28 (Page No. 88)
Convert the following regular expressions to $NFA's$ using the procedure given in Theorem $1.54.$ In all parts, $Σ = \{a, b\}.$ $a(abb)^{*}\cup b$ $a^{+}\cup (ab)^{+}$ $(a\cup b^{+})a^{+}b^{+}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 4 views

0 votes

0 answers

6

Michael Sipser Edition 3 Exercise 1 Question 27 (Page No. 88)
Read the informal definition of the finite state transducer given in question $24.$ Give the state diagram of an $FST$ with the following behavior. Its input and output alphabets are $\{0,1\}.$ Its output string is ... the even positions but inverted on the odd positions. For example, on input $0000111$ it should output $1010010.$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

7

Michael Sipser Edition 3 Exercise 1 Question 26 (Page No. 87)
Using the solution you gave to question $25,$ give a formal description of the machines $T_{1}$ and $T_{2}$ depicted in question $24.$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

8

Michael Sipser Edition 3 Exercise 1 Question 25 (Page No. 87)
Read the informal definition of the finite state transducer given in question $24.$ Give a formal definition of this model, following the pattern in Definition $1.5$ $\text{(page 35).}$ Assume that an $FST$ has an input alphabet $Σ$ and an output ... $(Hint:$ An $FST$ is a $5$-tuple. Its transition function is of the form $δ : Q Σ→Q Γ.)$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

9

Michael Sipser Edition 3 Exercise 1 Question 24 (Page No. 87)
A $\text{finite state transducer (FST)}$ is a type of deterministic finite automaton whose output is a string and not just accept or reject. The following are state diagrams of finite state transducers $T1$ and $T2.$ Each transition of an $FST$ is labeled ... $\text{$T_{2}$ on input bbbbbb}$ h. $\text{$T_{2}$ on input $\epsilon$}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

10

Decidability and Undecidability
From where to learn the decidability and Undecidability concept for gate? So that I can grasp the full concept of that topic crystal clear..(please suggest me except Shai Simonson..I had already watch that video but i could'nt clear my concepts from there) i am facing real difficulty on that topic

asked 1 day ago in Theory of Computation by Ritabrata Dey (37 points) | 8 views

0 votes

0 answers

11

Michael Sipser Edition 3 Exercise 1 Question 23 (Page No. 87)
Let $B$ be any language over the alphabet $Σ.$ Prove that $B = B^{+}$ iff $BB ⊆ B.$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

12

Michael Sipser Edition 3 Exercise 1 Question 22 (Page No. 87)
In certain programming languages, comments appear between delimiters such as $\text{/#}$ and $\text{#/}.$ Let $C$ be the language of all valid delimited comment strings. A member of $C$ must begin with $\text{/#}$ ... $DFA$ that recognizes $C.$ b. Give a regular expression that generates $C.$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 5 views

0 votes

0 answers

13

Michael Sipser Edition 3 Exercise 1 Question 21 (Page No. 86)
Use the procedure described in $\text{Lemma 1.60}$ to convert the following finite automata to regular expressions.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

14

Michael Sipser Edition 3 Exercise 1 Question 20 (Page No. 86)
For each of the following languages, give two strings that are members and two strings that are not members-a total of four strings for each part. Assume the alphabet $Σ = \{a,b\}$ in all parts. $a^{*}b^{*}$ $a(ba)^{*}b$ $a^{*}\cup b^{*}$ ... $aba\cup bab$ $(\epsilon\cup a)b$ $(a\cup ba\cup bb)\sum^{*}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

15

Michael Sipser Edition 3 Exercise 1 Question 19 (Page No. 86)
Use the procedure described in $\text{Lemma 1.55}$ to convert the following regular expressions to non-deterministic finite automata. $(0\cup 1)^{*}000(0\cup 1)^{*}$ $(((00)^{*}(11))\cup 01)^{*}$ $\phi^{*}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 4 views

0 votes

0 answers

16

Michael Sipser Edition 3 Exercise 1 Question 18 (Page No. 86)
Give regular expressions generating the languages of the alphabet is $\{0,1\}.$ $\text{\{w| w begins with a 1 and ends with a 0\}}$ $\text{\{w| w contains at least three 1s\}}$ ... $\text{The empty set}$ $\text{All strings except the empty string}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 6 views

0 votes

0 answers

17

Michael Sipser Edition 3 Exercise 1 Question 17 (Page No. 86)
Give an $NFA$ recognizing the language $(01 ∪ 001 ∪ 010)^{*}.$ Convert this $NFA$ to an equivalent $DFA.$ Give only the portion of the $DFA$ that is reachable from the start state.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

18

Michael Sipser Edition 3 Exercise 1 Question 16 (Page No. 86)
Use the construction given in $\text{Theorem 1.39}$ to convert the following two non-deterministic finite automata to equivalent deterministic finite automata.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

19

Michael Sipser Edition 3 Exercise 1 Question 15 (Page No. 85)
Give a counterexample to show that the following construction fails to prove $\text{Theorem 1.49,}$ the closure of the class of regular languages under the star operation$.$ Let $N_{1} = (Q_1, Σ, δ_1, q_1, F_1)$ ... , $N1,$ for which the constructed automaton $N$ does not recognize the star of $N_{1}^{'s}$ language.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

20

Michael Sipser Edition 3 Exercise 1 Question 14 (Page No. 85)
Show that if $M$ is a $DFA$ that recognizes language $B,$ swapping the accept and not accept states in $M$ yields a new $DFA$ recognizing the complement of $B.$ Conclude that the class of regular languages is closed under ... of $C.$ Is the class of languages recognized by $NFA's$ closed under complement$?$ Explain your answer$.$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

21

Michael Sipser Edition 3 Exercise 1 Question 13 (Page No. 85)
Let $F$ be the language of all strings over $\{0,1\}$ that do not contain a pair of $1's$ that are separated by an odd number of symbols. Give the state diagram of a $\text{DFA}$ with five states that recognizes $F.$ $($You may find it helpful first to find a $4$-state $\text{NFA}$ for the complement of $F.)$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 5 views

0 votes

0 answers

22

Michael Sipser Edition 3 Exercise 1 Question 12 (Page No. 85)
Let $\text{D = \{w| w contains an even number of a’s and an odd number of b’s and does not contain the substring ab\}}.$ Give a $\text{DFA}$ with five states that recognizes $\text{D}$ and a regular expression that generates $\text{D.}$ $($Suggestion: Describe $D$ more simply$.)$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

+1 vote

1 answer

23

If there is an $\rm NP$-complete language $L$ whose complement is in $\rm NP$, then...

answered 1 day ago in Theory of Computation by Pragy Agarwal Boss (22.2k points) | 56 views

0 votes

0 answers

24

Michael Sipser Edition 3 Exercise 1 Question 11 (Page No. 85)
Prove that every $\text{NFA}$ can be converted to an equivalent one that has a single accept state.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 6 views

0 votes

0 answers

25

Michael Sipser Edition 3 Exercise 1 Question 10 (Page No. 85)
Use the construction in the proof of $\text{Theorem 1.49}$ to give the state diagrams of $NFA's$ recognizing the star of the languages described in $\text{\{w| w contains at least three 1s\}}$ $\text{\{w| w contains at least two 0's and at most one 1\}}$ $\text{The empty set}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

26

Michael Sipser Edition 3 Exercise 1 Question 9 (Page No. 85)
Use the construction in the proof of $\text{Theorem 1.47}$ to give the state diagrams of $\text{NFA's}$ recognizing the concatenation of the languages described in $\text{\{w| the length of w is at most 5\}}$ $\text{\{w| every odd position of w is a 1\}}$ $\text{\{w| w contains at least three 1s\}}$ $\text{The empty set}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 3 views

0 votes

0 answers

27

Michael Sipser Edition 3 Exercise 1 Question 8 (Page No. 84)
Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA's}$ recognizing the union of the languages described in $\text{\{w| w begins with a 1 and ends with a 0\}}$ ... $\text{\{w| w doesn't contain the substring 110\}}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 4 views

0 votes

0 answers

28

Michael Sipser Edition 3 Exercise 1 Question 7 (Page No. 84)
Give state diagrams of $\text{NFA's}$ with the specified number of states recognizing each of the following languages. In all parts, the alphabet is $\{0,1\}.$ $\text{The language \{w| w ends with 00\} with three states}$ ... $\text{The language}$ $\{\epsilon\}$ $\text{with one state}$ $\text{The language 0* with one state}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 4 views

0 votes

0 answers

29

Michael Sipser Edition 3 Exercise 1 Question 6 (Page No. 84)
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is $\{0,1\}.$ $\text{\{w| w begins with a 1 and ends with a 0\}}$ $\text{\{w| w contains at least three 1s\}}$ ... $\text{The empty set}$ $\text{All strings except the empty string}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 5 views

0 votes

0 answers

30

Michael Sipser Edition 3 Exercise 1 Question 4 (Page No. 83)
Each of the following languages is the intersection of two simpler languages. In each part, construct $\text{DFAs}$ for the simpler languages, then combine them using the construction discussed in footnote $\text{3 (page 46)}$ to give the state diagram of ... $\text{\{w| w has even length and an odd number of a's\}}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

0 votes

0 answers

31

Michael Sipser Edition 3 Exercise 1 Question 3 (Page No. 83)
The formal description of a $\text{DFA}$ $\text{M}$ is $({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}),$ where $\text{δ}$ is given by the following table. Give the state diagram of this machine.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 7 views

0 votes

0 answers

32

Michael Sipser Edition 3 Exercise 1 Question 2 (Page No. 83)
Give the formal description of the machines $\text{M1}$ and $\text{M2.}$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 4 views

0 votes

0 answers

33

Michael Sipser Edition 3 Exercise 1 Question 1 (Page No. 83)
The following are the state diagrams of two $\text{DFAs,}$ $\text{M1}$, and $\text{M2.}$ Answer the following questions about each of these machines. What is the start state? What is the set of accept states? What sequence ... $\text{aabb?}$ Does the machine accept the string $\text{aabb?}$ Does the machine accept the string $\epsilon?$

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Boss (34.5k points) | 2 views

+1 vote

1 answer

34

Toc p and np
Are p and np problems both closed under union intersection and concatenation and kleene closure? If yes then how?

answered 1 day ago in Theory of Computation by Pragy Agarwal Boss (22.2k points) | 59 views

+1 vote

1 answer

35

P and NP Question doubt
What will be the answer to this question? L’ is the complement of language L belongs to NP does not always imply that L’ belongs to NP L’ belongs to P both a and b

answered 2 days ago in Theory of Computation by Pragy Agarwal Boss (22.2k points) | 139 views

0 votes

0 answers

36

Peter Linz Edition 4 Exercise 7.1 Question 9 (Page No. 183)
Is it possible to find a dfa that accepts the same language as the pda $M= (${$q_0,q_1$},{$a,b$},{$z$},$\delta,q_0,z,${$q_1$}), with $\delta(q_0,a,z)=${$(q_1,z)$}, $\delta(q_0,b,z)=${$(q_0,z)$}, $\delta(q_1,a,z)=${$(q_1,z)$}, $\delta(q_1,b,z)=${$(q_0,z)$} ?

asked 2 days ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 6 views

0 votes

0 answers

37

Peter Linz Edition 4 Exercise 7.1 Question 8 (Page No. 183)
Find an npda for the language $L =$ {$ab (ab)^n b (ba)^n : n ≥ 0$}.

asked 2 days ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 3 views

0 votes

0 answers

38

Peter Linz Edition 4 Exercise 7.1 Question 7 (Page No. 183)
Find an npda for the concatenation of $L (a^*)$ and the language in Exercise 6.

asked 2 days ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 4 views

0 votes

0 answers

39

Peter Linz Edition 4 Exercise 7.1 Question 6 (Page No. 183)
Find an npda on $Σ =$ {$a, b, c$} that accepts the language $L=${$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2^R$}.

asked 2 days ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 3 views

0 votes

0 answers

40

Peter Linz Edition 4 Exercise 7.1 Question 5 (Page No. 183)
Construct an npda that accepts the language $L =$ {$a^nb^m : n ≥ 0, n ≠ m$}.

asked 2 days ago in Theory of Computation by Naveen Kumar 3 Loyal (7.1k points) | 2 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