The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
+3
votes
6
answers
1
ISRO202041
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
asked
Jan 14
in
Theory of Computation
by
Satbir

615
views
isro2020
theoryofcomputation
finiteautomata
normal
0
votes
0
answers
2
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

89
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
3
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
4
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 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

29
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
5
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 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

22
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
6
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 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

31
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
7
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

16
views
michaelsipser
theoryofcomputation
finiteautomata
decidability
proof
0
votes
0
answers
8
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

28
views
michaelsipser
theoryofcomputation
turingmachine
finiteautomata
decidability
proof
0
votes
0
answers
9
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

66
views
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
decidability
proof
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 4 Question 1 (Page No. 210)
asked
Oct 16, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

37
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
descriptive
0
votes
1
answer
11
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 14, 2019
in
Theory of Computation
by
gatecse

131
views
cmi2019
finiteautomata
nfadfa
+1
vote
1
answer
12
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 14, 2019
in
Theory of Computation
by
gatecse

108
views
cmi2018
finiteautomata
nfadfa
descriptive
+2
votes
3
answers
13
UGCNETJune2019II: 75
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 3, 2019
in
Theory of Computation
by
Arjun

829
views
ugcnetjune2019ii
finiteautomata
minimalstateautomata
+2
votes
2
answers
14
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 4, 2019
in
Theory of Computation
by
Akash Kumar Roy

459
views
theoryofcomputation
finiteautomata
regulargrammar
+3
votes
3
answers
15
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 23, 2019
in
Theory of Computation
by
Hirak

387
views
acetestseries
theoryofcomputation
finiteautomata
numberofdfa
+2
votes
0
answers
16
Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
asked
May 10, 2019
in
Theory of Computation
by
logan1x

197
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguages
context
0
votes
0
answers
17
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

77
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
18
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

76
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
19
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

78
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
20
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

47
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
21
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

73
views
michaelsipser
theoryofcomputation
finiteautomata
homomorphism
descriptive
0
votes
0
answers
22
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

38
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
23
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

73
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
24
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

36
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
25
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

37
views
michaelsipser
theoryofcomputation
finiteautomata
descriptive
0
votes
0
answers
26
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

34
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
1
answer
27
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

70
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
28
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

52
views
michaelsipser
theoryofcomputation
finiteautomata
synchronizabledfa
descriptive
0
votes
0
answers
29
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

47
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
30
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
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

97
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
Page:
1
2
3
4
5
6
...
28
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged finiteautomata
Recent Blog Comments
Thank brother !! Bookmarked it :)
Check out goxul.github.io, it has all the...
congratulation brother ! Can you please tell me...
I got selected for this, in case someone lands up...
After the written exam and at the time of...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,581
answers
202,000
comments
95,401
users