The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged theoryofcomputation
Webpage for Theory of Computation:
0
votes
0
answers
1
Made Easy Test Series: TOC
The pushdown automata $M=\left \{ \left ( q_{0},q_{1},q_{2} \right ),\left ( a,b \right ) ,\left ( 0,1 \right ),\partial ,q_{0},0,\left \{ q_{0} \right \}\right \}$ $\partial \left ( q_{0},a,0 \right )=\left ( q_{1},10 \right )$ ... $q_{0}$ As last transition going from $q_{2}$ to $q_{0}$ and not $q_{0}$ to $q_{2}$ Am I right?
asked
1 hour
ago
in
Theory of Computation
by
srestha
Veteran
(
111k
points)

3
views
theoryofcomputation
madeeasytestseries
0
votes
1
answer
2
Made Easy Test Series:TOCDFA
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________ Answer will be $3$ or $6?$
asked
9 hours
ago
in
Theory of Computation
by
srestha
Veteran
(
111k
points)

19
views
theoryofcomputation
testseries
madeeasytestseries
0
votes
0
answers
3
SelfDoubt(PNP class)
$1)$ If the complement of NPComplete problem is in NP, then can we also say , for this case complement of NP problem is in NPComplete ? $2)$ If the complement of NPComplete problem is in CoNP, then can we also say, for this case complement of CoNP problem is in NPComplete?
asked
1 day
ago
in
Theory of Computation
by
srestha
Veteran
(
111k
points)

41
views
pnpnpcnph
theoryofcomputation
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

20
views
michaelsipser
theoryofcomputation
finiteautomata
pumpinglemma
proof
0
votes
1
answer
5
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}=\{wwww\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.)}$
asked
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

14
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
0
votes
0
answers
6
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
7
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
fst
descriptive
0
votes
0
answers
8
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

2
views
michaelsipser
theoryofcomputation
finiteautomata
fst
descriptive
0
votes
0
answers
9
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
finitestatetransducer
0
votes
0
answers
10
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

2
views
michaelsipser
theoryofcomputation
finite
state
transducer
finiteautomata
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
regularlanguages
proof
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

5
views
michaelsipser
theoryofcomputation
regularexpressions
finiteautomata
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
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 membersa 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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

4
views
michaelsipser
theoryofcomputation
regularlanguages
regularexpressions
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 nondeterministic finite automata. $(0\cup 1)^{*}000(0\cup 1)^{*}$ $(((00)^{*}(11))\cup 01)^{*}$ $\phi^{*}$
asked
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

5
views
michaelsipser
theoryofcomputation
regularexpressions
nfa
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

6
views
michaelsipser
theoryofcomputation
regularexpressions
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
nfadfa
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 nondeterministic finite automata to equivalent deterministic finite automata.
asked
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

2
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

2
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

8
views
michel
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
0
votes
0
answers
23
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

6
views
michaelsipser
theoryofcomputation
nfa
proof
0
votes
0
answers
24
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
0
answers
25
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
0
votes
0
answers
26
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
0
answers
27
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
statediagram
descriptive
0
votes
0
answers
28
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
statediagram
descriptive
+1
vote
1
answer
29
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\}}$
asked
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

22
views
michaelsipser
theoryofcomputation
finiteautomata
finiteautomata
descriptive
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
2 days
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
34.5k
points)

2
views
michaelsipser
theoryofcomputation
finiteautomata
statediagram
descriptive
Page:
1
2
3
4
5
6
...
121
next »
Quick search syntax
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 Posts
IIT BHUBANESWAR MTECH WRITTEN TEST/INTERVIEW
GATE score validity queries.
How to prepare for IISC Interdisciplinary Mathematical Sciences Interview
GO Hardcopy for GATE 2020
How to prepare for BARC interview
Follow @csegate
Recent questions tagged theoryofcomputation
Recent Blog Comments
10000 to <2000 is really kind of achievement , my...
THey removed it this year... I did not check it,...
even though i am not going for iiit , can you...
I don't think IIITD requires any codechef...
Will apply for IIITB. IIIT D requires a codechef...
50,122
questions
53,241
answers
184,705
comments
70,480
users