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
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 finiteautomata
Some useful problems
0
votes
1
answer
1
UGCNETJune2019II75
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
413k
points)

15
views
ugcnetjune2019ii
finiteautomata
0
votes
2
answers
2
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
(
529
points)

97
views
theoryofcomputation
finiteautomata
regulargrammar
+1
vote
3
answers
3
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.3k
points)

120
views
acetestseries
theoryofcomputation
finiteautomata
numberofdfa
+1
vote
0
answers
4
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
(
395
points)

99
views
theoryofcomputation
finiteautomata
ambiguous
regularlanguages
contextfreelanguage
context
0
votes
0
answers
5
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
Boss
(
41.5k
points)

14
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
6
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
Boss
(
41.5k
points)

16
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
7
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
Boss
(
41.5k
points)

10
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
8
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
Boss
(
41.5k
points)

13
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
proof
descriptive
0
votes
0
answers
9
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
Boss
(
41.5k
points)

16
views
michaelsipser
theoryofcomputation
finiteautomata
homomorphism
descriptive
0
votes
0
answers
10
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
Boss
(
41.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
nfadfa
descriptive
0
votes
0
answers
11
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
Boss
(
41.5k
points)

11
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
0
answers
12
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
Boss
(
41.5k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
13
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
Boss
(
41.5k
points)

11
views
michaelsipser
theoryofcomputation
finiteautomata
descriptive
0
votes
0
answers
14
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
Boss
(
41.5k
points)

7
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
1
answer
15
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
Boss
(
41.5k
points)

23
views
michaelsipser
theoryofcomputation
finiteautomata
nfa
descriptive
0
votes
0
answers
16
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
Boss
(
41.5k
points)

17
views
michaelsipser
theoryofcomputation
finiteautomata
synchronizabledfa
descriptive
0
votes
0
answers
17
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
Boss
(
41.5k
points)

24
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
1
answer
18
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
Boss
(
41.5k
points)

23
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
pumpinglemma
proof
descriptive
0
votes
0
answers
19
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
Boss
(
41.5k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 1 Question 52 (Page No. 91)
$\text{MyhillNerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ by $L$ if every two distinct strings in $X$ are ... $\text{DFA}$ recognizing it$.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

9
views
michaelsipser
theoryofcomputation
finiteautomata
finiteautomata
proof
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 1 Question 51 (Page No. 90)
Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the strings $xz$ and $yz$ ... $≡L$ is an equivalence relation. A $\text{palindrome}$ is a string that reads the same forward and backward.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
proof
descriptive
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 1 Question 50 (Page No. 90)
Read the informal definition of the finite state transducer given in Question $24.$ Prove that $\text{no FST}$ can output $w^{R}$ for every input $w$ if the input and output alphabets are $\{0,1\}.$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
finitestatetransducer
proof
descriptive
0
votes
1
answer
23
Michael Sipser Edition 3 Exercise 1 Question 49 (Page No. 90)
Let $B=\{1^{k}yy\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}yy\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

18
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 1 Question 48 (Page No. 90)
Let $\sum = \{0,1\}$ and let $D = \{ww$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$ Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

3
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 1 Question 47 (Page No. 90)
Let $\sum=\{1,\#\}$ and let $Y=\{ww=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

5
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 1 Question 46 (Page No. 90)
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}m,n\geq 0\}$ $\{0^{m}1^{n}m\neq n\}$ $\{ww\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtww,t\in\{0,1\}^{+}\}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 1 Question 45 (Page No. 90)
Let $\text{A/B = {w wx ∈ A for some x ∈ B}}.$ Show that if $A$ is regular and $B$ is any language, then $\text{A/B}$ is regular.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

4
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 1 Question 44 (Page No. 90)
Let $B$ and $C$ be languages over $\sum = \{0, 1\}.$ Define $B\overset{1}{\leftarrow} C = \{w\in B$ $\text{for some}$ $y\in C$, $\text{strings}$ $w$ $\text{and}$ $y$ $\text{contain equal numbers of}$ $1’s\}.$ Show that the class of regular languages is closed under the $\overset{1}{\leftarrow}$operation.
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

2
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
descriptive
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 1 Question 43 (Page No. 90)
Let $A$ be any language. Define $\text{DROPOUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\text{DROPOUT(A) = $\{xz xyz\in A$ where $x, ... $\text{Theorem 1.47.}$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

8
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
proof
descriptive
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 1 Question 42 (Page No. 89)
For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of regular languages is closed under shuffle.
asked
Apr 29
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
41.5k
points)

13
views
michaelsipser
theoryofcomputation
finiteautomata
regularlanguages
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
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Interview Experience at IITPalakkad
Follow @csegate
Recent questions tagged finiteautomata
Recent Blog Comments
Hi, the previous email was sent to only those who...
@kriti05 can you please tell me when did you got...
It was said that there will be an address...
sir .I recvd a mail which states "Your...
49,808
questions
54,489
answers
188,271
comments
74,682
users