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
+1
vote
2
answers
1
ISRO202041
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
24.2k
points)

184
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
Veteran
(
59.3k
points)

19
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
Veteran
(
59.3k
points)

10
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 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

8
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 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

7
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 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

7
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
Veteran
(
59.3k
points)

3
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
Veteran
(
59.3k
points)

9
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
Veteran
(
59.3k
points)

19
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
Veteran
(
59.3k
points)

10
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 13, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

65
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 13, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

41
views
cmi2018
finiteautomata
nfadfa
descriptive
+2
votes
2
answers
13
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, 2019
in
Theory of Computation
by
Arjun
Veteran
(
431k
points)

350
views
ugcnetjune2019ii
finiteautomata
minimalstateautomata
0
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 3, 2019
in
Theory of Computation
by
Akash Kumar Roy
Junior
(
559
points)

237
views
theoryofcomputation
finiteautomata
regulargrammar
+2
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 22, 2019
in
Theory of Computation
by
Hirak
Active
(
3.6k
points)

237
views
acetestseries
theoryofcomputation
finiteautomata
numberofdfa
+1
vote
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
Active
(
1.2k
points)

137
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

54
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

35
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

27
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

22
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

28
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

14
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

32
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

14
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

16
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

14
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

35
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

25
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

28
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
Apr 30, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
59.3k
points)

54
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged finiteautomata
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,548
comments
105,365
users