Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
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?
Can somebody explainWhat is identity permutation?
srestha
313
views
srestha
asked
Apr 1, 2019
Combinatory
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.
Show that given a regular language $L$, its minimal dfa is unique within a simple relabeling ofthe states.
Naveen Kumar 3
288
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Write a Computer program that produces a minimal dfa for any given dfa.
Naveen Kumar 3
340
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Prove the following: If the states $q_a$ and $q_b$ are indistinguishable, and if $q_a$ and $q_c$ aredistinguishable, then $q_b$ and $q_c$ must be distinguishable.
Naveen Kumar 3
262
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Show that indistinguishability is an equivalence relation but that distinguishability is not.
Naveen Kumar 3
288
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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}$.
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 d...
Naveen Kumar 3
209
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Show that if $L$ is a nonempty language such that any $w$ in $L$ has length at least $n$, then any dfaaccepting $L$ must have at least $n + 1$ states.
Naveen Kumar 3
476
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Minimize the states in the dfa depicted in the following diagram.
Naveen Kumar 3
1.0k
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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$}.
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:...
Naveen Kumar 3
643
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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:
Minimize the number of states in the dfa of following figure:
Naveen Kumar 3
544
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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)$.
Let $L$ be any language. Define $even (w)$ as the string obtained by extracting from $w$ the letters ineven-numbered positions; that is, if $w = a_1a_2a_3a_4…$...
Naveen Kumar 3
357
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
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
453
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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$.
Show that if $L$ is regular, so is $L^R$.
Naveen Kumar 3
189
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Prove that all finite languages are regular.
Naveen Kumar 3
204
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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?
Define a dfa with multiple initial states in an analogous way to the corresponding nfa in Exercise18, Section 2.2. Does there always exist an equivalent dfa with a single...
Naveen Kumar 3
299
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
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$.
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
666
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
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$}.
Find an nfa without $λ$-transitions and with a single final state that accepts the set {$a$} $∪$ {$b^n : n ≥1$}.
Naveen Kumar 3
1.7k
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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?
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with onlyone final state. Can we make a similar claim for dfa’s?
Naveen Kumar 3
1.8k
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
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. ...
Naveen Kumar 3
221
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
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...
Naveen Kumar 3
213
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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$.
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,�...
Naveen Kumar 3
147
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
proof
+
–
1
votes
0
answers
322
Peter Linz Edition 4 Exercise 2.3 Question 3 (Page No. 62)
Convert the following nfa into an equivalent dfa.
Convert the following nfa into an equivalent dfa.
Naveen Kumar 3
957
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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.
Convert the nfa in following figure, into an equivalent dfa.
Naveen Kumar 3
594
views
Naveen Kumar 3
asked
Mar 30, 2019
Theory of Computation
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?
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 o...
aditi19
1.5k
views
aditi19
asked
Mar 24, 2019
Theory of Computation
theory-of-computation
finite-automata
virtual-gate-test-series
+
–
1
votes
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?
Theorem: Let $L$ be the language accepted by a nondeterministic finite accepter $M_N= (Q_N, Σ,δ N,q0,F_N)$. Thenthere exists a deterministic finite accepter $M_D= (Q_D,...
Naveen Kumar 3
350
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
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
An nfa in which (a) there are no λ-transitions, and (b) for all $q ∈ Q$ and all $a ∈ Σ$, $δ (q,a)$containsat most one element, is sometimes called an incomplete df...
Naveen Kumar 3
1.0k
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
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 ∈ Σ^*$.]
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 ...
Naveen Kumar 3
205
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
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)
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 ...
Naveen Kumar 3
305
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
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)
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...
Naveen Kumar 3
862
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
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$} .
Let $L$ be the language accepted by the nfa in the following figure:Find an nfa that accepts $L$ $∪$ {$a^5$} .
Naveen Kumar 3
412
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
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 »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register