The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Recent questions tagged finiteautomata
Some useful problems
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A twodimensional finite automaton $(2DIMDFA)$ 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
(
53.4k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a twoheaded finite automaton $(2DFA)$ to be a deterministic finite automaton that has two readonly, bidirectional heads that start at the lefthand 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
(
53.4k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 4 Question 27 (Page No. 212)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
asked
Oct 17
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 4 Question 26 (Page No. 212)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
asked
Oct 17
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 4 Question 25 (Page No. 212)
Let $BAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some string containing an equal number of 0s and 1s}\}$. Show that $BAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)
asked
Oct 17
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

2
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 4 Question 17 (Page No. 212)
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
asked
Oct 17
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 4 Question 3 (Page No. 211)
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
asked
Oct 16
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
finiteautomata
decidability
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
asked
Oct 16
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

12
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
decidability
proof
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 4 Question 1 (Page No. 210)
asked
Oct 16
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
descriptive
0
votes
1
answer
10
CMI2019A2
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true? The shortest word in $L(A)$ has length at most $n1.$ The shortest word in $L(A)$ has length at least $n.$ The shortest word not in $L(A)$ has length at most $n1.$ The shortest word not in $L(A)$ has length at least $n.$
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.6k
points)

41
views
cmi2019
finiteautomata
nfa
+1
vote
1
answer
11
CMI2018B1
Consider the following nondeterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
asked
Sep 13
in
Theory of Computation
by
gatecse
Boss
(
16.6k
points)

22
views
cmi2018
finiteautomata
nfadfa
descriptive
+2
votes
2
answers
12
UGCNETJune2019II75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
423k
points)

229
views
ugcnetjune2019ii
finiteautomata
minimalstateautomata
0
votes
2
answers
13
Conversion of regular grammar to FA
A>aB/bA/b B>aC/bB C>aA/bC/a If the above regular grammar is converted into DFA then how many final states will be there? According to me there should be 2 final states: A and C But the resource from where I am reading it says only one final state will be there which will be A. Kindly explain.
asked
Jun 3
in
Theory of Computation
by
Akash Kumar Roy
Junior
(
559
points)

177
views
theoryofcomputation
finiteautomata
regulargrammar
+2
votes
3
answers
14
Ace Test Series: Theory Of Computation  Finite Automata
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
asked
May 22
in
Theory of Computation
by
Hirak
Active
(
3.5k
points)

205
views
acetestseries
theoryofcomputation
finiteautomata
numberofdfa
+1
vote
0
answers
15
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
asked
May 10
in
Theory of Computation
by
logan1x
Junior
(
803
points)

119
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $s < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $s < k1k2.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

48
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
17
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

29
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
18
Michael Sipser Edition 3 Exercise 1 Question 70 (Page No. 93)
We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove that the class of regular languages is closed under the ${avoids}$ operation.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

23
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{www\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

20
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 1 Question 66 (Page No. 93)
A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w_{1})f(w_{2})...f(w_{n}),$ ... Is it a DFA in every case$?$ Show, by giving an example, that the class of nonregular languages is not closed under homomorphism.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

20
views
michaelsipser
theoryofcomputation
finiteautomata
homomorphism
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 1 Question 65 (Page No. 93)
Prove that for each $n > 0,$ a language $B_{n}$ exists where $B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, and if $B_{n} = A_{1}\cup...\cup A_{k},$ for regular languages $A_{i},$ then at least one of the $A_{i}$ requires a $\text{DFA}$ with exponentially many states$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

9
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 1 Question 64 (Page No. 92)
Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$ Show that if $A$ is nonempty, A contains some string of length at most k. Show, by giving an example, that $\text{part (a)}$ is not necessarily ... $k.$ Come as close to the bound in $(c)$ as you can$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

29
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 1 Question 63 (Page No. 92)
Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets. Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if $B\subseteq D$ and $D$ contains infinitely many ... regular languages where $B\subseteqq D,$ then we can find a regular language $C$ where $B\subseteqq C\subseteqq D.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 1 Question 62 (Page No. 92)
Let $\sum =\{a, b\}.$ For each $k\geq 1,$ let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols$.$Thus $D_{k}=\sum^{*}a(\sum \cup \epsilon)^{k1}$.Describe a $\text{DFA}$ with at most $k+ 1$ states that recognizes $D_{k}$ in terms of both a state diagram and a formal description.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

15
views
michaelsipser
theoryofcomputation
finiteautomata
descriptive
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 1 Question 61 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the righthand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

12
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
1
answer
26
Michael Sipser Edition 3 Exercise 1 Question 60 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the righthand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k1}.$ Describe an $\text{NFA}$ with $k + 1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

29
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 1 Question 59 (Page No. 92)
Let $M = (Q, Σ, δ, q_{0}, F)$ be a $\text{DFA}$ and let $h$ be a state of $M$ called its $\text{ home }.$ A $\text{synchronizing sequence}$ for $M$ and $h$ is a string $s\in\sum^{*}$ ... $\text{DFA,}$ then it has a synchronizing sequence of length at most $k^{3}.$Can you improve upon this bound$?$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

23
views
michaelsipser
theoryofcomputation
finiteautomata
synchronizabledfa
descriptive
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 1 Question 56 (Page No. 91)
If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w w is the representation in base k of some number in A\}}.$ Here, we do not allow leading $0's$ in the representation of a ... a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular$.$ Prove that your example works.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

27
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
29
Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)
Consider the language $F=\{a^{i}b^{j}c^{k}i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$ Show that $F$ is not regular. Show that $F$ acts like a regular language in the pumping lemma. ... three conditions of the pumping lemma for this value of $p.$ Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

47
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+zx,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
53.4k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
Page:
1
2
3
4
5
6
...
27
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
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Follow @csegate
Recent questions tagged finiteautomata
Recent Blog Comments
still it's usefull for practice purpose and...
@Satbir Its a valuable info..Thanks
It is the 2019 question paper given as a mock...
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
50,650
questions
56,185
answers
193,939
comments
94,694
users