Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Some useful problems
Recent questions tagged finite-automata
0
votes
0
answers
301
General Query: Self doubt(Math+Automata)
Can somebody explain What is identity permutation?
srestha
asked
in
Combinatory
Apr 1, 2019
by
srestha
331
views
discrete-mathematics
finite-automata
0
votes
0
answers
302
Peter Linz Edition 5 Exercise 2.4 Question 10
Show that given a regular language $L$, its minimal dfa is unique within a simple relabeling of the states.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
291
views
peter-linz
peter-linz-edition5
theory-of-computation
finite-automata
0
votes
0
answers
303
Peter Linz Edition 4 Exercise 2.4 Question 9 (Page No. 69)
Write a Computer program that produces a minimal dfa for any given dfa.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
345
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
304
Peter Linz Edition 4 Exercise 2.4 Question 10 (Page No. 69)
Prove the following: If the states $q_a$ and $q_b$ are indistinguishable, and if $q_a$ and $q_c$ are distinguishable, then $q_b$ and $q_c$ must be distinguishable.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
275
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
305
Peter Linz Edition 4 Exercise 2.4 Question 7 (Page No. 69)
Show that indistinguishability is an equivalence relation but that distinguishability is not.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
293
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
306
Peter Linz Edition 4 Exercise 2.4 Question 6 (Page No. 69)
Prove or disprove the following conjecture. If $M = (Q,Σ,δ,q_0,F)$ is a minimal dfa for a regular language $L$, then $\widehat{M}= (Q, Σ,δ,q_0,Q – F)$ is a minimal dfa for $\overline{L}$.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
215
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
307
Peter Linz Edition 4 Exercise 2.4 Question 5 (Page No. 69)
Show that if $L$ is a nonempty language such that any $w$ in $L$ has length at least $n$, then any dfa accepting $L$ must have at least $n + 1$ states.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
479
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
8
votes
0
answers
308
Peter Linz Edition 4 Exercise 2.4 Question 4 (Page No. 69)
Minimize the states in the dfa depicted in the following diagram.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
1.0k
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
309
Peter Linz Edition 4 Exercise 2.4 Question 2 (Page No. 68)
Find minimal dfa's for the following languages. In each case prove that the result is minimal. (a) $L =$ {$a^n b^m :n≥2,m≥1$}. (b) $L =$ {$a^n b:n ≥0$} $∪$ {$b^n a:n ≥1$} (c) $L =$ {$a^n :n ≥ 0,n ≠ 3$}. (d) $L =$ {$a^n:n ≠ 2$ and $n ≠4$}. (e) $L =$ {$a^n:n$ mod $3 = 0$} $∪$ {$a^n: n$ mod $5 = 1$}.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
644
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
310
Peter Linz Edition 4 Exercise 2.4 Question 1 (Page No. 68)
Minimize the number of states in the dfa of following figure:
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
551
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
311
Peter Linz Edition 4 Exercise 2.3 Question 14 (Page No. 62)
Let $L$ be any language. Define $even (w)$ as the string obtained by extracting from $w$ the letters in even-numbered positions; that is, if $w = a_1a_2a_3a_4…$, then $even (w)= a_2a_4.…$ Corresponding to this, we can define a language $even (L) =$ {$even (w): w ∈ L$}. Prove that if $L$ is regular, so is $even(L)$.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
362
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
2
votes
0
answers
312
Peter Linz Edition 4 Exercise 2.3 Question 13 (Page No. 62)
Give a simple verbal description of the language accepted by the dfa in following figure. Use this to find another dfa, equivalent to the given one, but with fewer states.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
460
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
313
Peter Linz Edition 4 Exercise 2.3 Question 12 (Page No. 62)
Show that if $L$ is regular, so is $L^R$.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
195
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
0
votes
0
answers
314
Peter Linz Edition 4 Exercise 2.3 Question 11 (Page No. 62)
Prove that all finite languages are regular.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
210
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
0
votes
0
answers
315
Peter Linz Edition 4 Exercise 2.3 Question 10 (Page No. 62)
Define a dfa with multiple initial states in an analogous way to the corresponding nfa in Exercise 18, Section 2.2. Does there always exist an equivalent dfa with a single initial state?
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
305
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
1
vote
1
answer
316
Peter Linz Edition 4 Exercise 2.3 Question 9 (Page No. 62)
Let $L$ be a regular language that does not contain $λ$. Show that there exists an nfa without $λ$- transitions and with a single final state that accepts $L$.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
676
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
1
vote
1
answer
317
Peter Linz Edition 4 Exercise 2.3 Question 8 (Page No. 62)
Find an nfa without $λ$-transitions and with a single final state that accepts the set {$a$} $∪$ {$b^n : n ≥1$}.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
1.7k
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
1
answer
318
Peter Linz Edition 4 Exercise 2.3 Question 7 (Page No. 62)
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we make a similar claim for dfa’s?
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
1.8k
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
319
Peter Linz Edition 4 Exercise 2.3 Question 6 (Page No. 62)
Is it true that for every nfa $M = (Q,Σ,δ,q_0,F)$ the complement of $L(M)$ is equal to the set {$w ∈ Σ^*: δ^*(q_0,w) $ $\cap$ $(Q-F)$ $\neq$ $Ø$}? If so, prove it. If not, give a counterexample.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
227
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
320
Peter Linz Edition 4 Exercise 2.3 Question 5 (Page No. 62)
Is it true that for any nfa $M = (Q,Σ,δ,q_0,F)$ the complement of $L(M)$ is equal to the set {$w ∈ Σ^*: δ^*(q_0,w) $ $\cap$ $F= Ø$}? If so, prove it. If not, give a counterexample.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
217
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
321
Peter Linz Edition 4 Exercise 2.3 Question 4 (Page No. 62)
Theorem: Let $L$ be the language accepted by a nondeterministic finite accepter $M_N=(Q_N,Σ,δ_N,q_0,F_N)$. Then there exists a deterministic finite accepter $M_D=(Q_D,Σ,δ_D,${$q_0$}$,F_D)$ such that $L=L(M_D)$. Prove this Theorem. Show in ... the label of $\delta ^*_D(q_0,w)$ contains $q_f$, then $\delta ^*_N(q_0,w)$ also contains $q_f$.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
149
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
proof
1
vote
0
answers
322
Peter Linz Edition 4 Exercise 2.3 Question 3 (Page No. 62)
Convert the following nfa into an equivalent dfa.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
961
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
1
answer
323
Peter Linz Edition 4 Exercise 2.3 Question 2 (Page No. 62)
Convert the nfa in following figure, into an equivalent dfa.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 30, 2019
by
Naveen Kumar 3
603
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
2
votes
1
answer
324
Virtual Gate Test Series: Theory Of Computation - Finite Automata
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything? answer is 20 or 64?
aditi19
asked
in
Theory of Computation
Mar 24, 2019
by
aditi19
1.6k
views
theory-of-computation
finite-automata
virtual-gate-test-series
1
vote
1
answer
325
Peter Linz Edition 4 Exercise 2.3 Question 1 (Page No. 62)
Theorem: Let $L$ be the language accepted by a nondeterministic finite accepter $M_N= (Q_N, Σ,δ N,q0,F_N)$. Then there exists a deterministic finite accepter $M_D= (Q_D, Σ,δ_D,${$q_0$}$,F_D)$ such that $L= L (M_D)$. convert the nfa in following figure to a dfa: Can you see a simpler answer more directly?
Naveen Kumar 3
asked
in
Theory of Computation
Mar 22, 2019
by
Naveen Kumar 3
362
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
1
vote
1
answer
326
Peter Linz Edition 4 Exercise 2.2 Question 21 (Page No. 56)
An nfa in which (a) there are no λ-transitions, and (b) for all $q ∈ Q$ and all $a ∈ Σ$, $δ (q,a)$contains at most one element, is sometimes called an incomplete dfa. This is reasonable since the conditions make it such that there is never any choice of moves. For $Σ = $ {$a,b$}, convert the incomplete dfa below into a standard dfa
Naveen Kumar 3
asked
in
Theory of Computation
Mar 22, 2019
by
Naveen Kumar 3
1.0k
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
327
Peter Linz Edition 4 Exercise 2.2 Question 20 (Page No. 56)
Show that for any nfa for all $q ∈Q$ and all $w, v ∈ Σ^*$ : $\delta ^*(q,wv)=\cup _{p\epsilon \delta ^*(q,w)}\delta ^*(p,v)$ [Use Definition: For an nfa, the extended transition function is defined so that $δ^* (q_i,w)$ ... walk in the transition graph from $q_i$ to $q_j$ labeled $w$. This holds for all $q_i, q_j ∈ Q$, and $w ∈ Σ^*$.]
Naveen Kumar 3
asked
in
Theory of Computation
Mar 22, 2019
by
Naveen Kumar 3
209
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
1
vote
0
answers
328
Peter Linz Edition 4 Exercise 2.2 Question 18 (Page No. 55)
An nfa with multiple initial states is defined by the quintuple $M =(Q, Σ,δ,q0,F)$, where $Q_0 ⊆ Q$ is a set of possible initial states. The language accepted by such an automaton is defined as $L (M)=$ ... the same language. Also, Suppose that we made the restriction $Q_0 ∩ F= Ø$. Would this affect the conclusion? (Question 19)
Naveen Kumar 3
asked
in
Theory of Computation
Mar 22, 2019
by
Naveen Kumar 3
310
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
1
answer
329
Peter Linz Edition 4 Exercise 2.2 Question 16 (Page No. 55)
Find an nfa that accepts {$a$}* and is such that if in its transition graph a single edge is removed (without any other changes), the resulting automaton accepts {$a$}. Can this be solved using a dfa? If so, give the solution; if not, give convincing arguments for your conclusion. (Question 17)
Naveen Kumar 3
asked
in
Theory of Computation
Mar 22, 2019
by
Naveen Kumar 3
868
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
0
votes
0
answers
330
Peter Linz Edition 4 Exercise 2.2 Question 14 (Page No. 55)
Let $L$ be the language accepted by the nfa in the following figure: Find an nfa that accepts $L$ $∪$ {$a^5$} .
Naveen Kumar 3
asked
in
Theory of Computation
Mar 22, 2019
by
Naveen Kumar 3
418
views
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
Page:
« prev
1
...
6
7
8
9
10
11
12
13
14
15
16
...
35
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged finite-automata
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...