Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Some useful problems
Recent questions tagged finite-automata
0
votes
1
answer
331
Peter Linz Edition 4 Exercise 2.2 Question 13 (Page No. 55)
What is the complement of the language accepted by the nfa in the following figure:
What is the complement of the language accepted by the nfa in the following figure:
Naveen Kumar 3
303
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
2
votes
1
answer
332
Peter Linz Edition 4 Exercise 2.2 Question 11 (Page No. 55)
Find an nfa with four states for $L$ = {$a^n: n ≥ 0$} $∪$ {$b^na: n ≥ 1$} .
Find an nfa with four states for $L$ = {$a^n: n ≥ 0$} $∪$ {$b^na: n ≥ 1$} .
Naveen Kumar 3
3.2k
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
333
Peter Linz Edition 4 Exercise 2.2 Question 8 (Page No. 55)
Construct an nfa with three states that accepts the language {$ab,abc$}*.
Construct an nfa with three states that accepts the language {$ab,abc$}*.
Naveen Kumar 3
434
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
334
Peter Linz Edition 4 Exercise 2.2 Question 7 (Page No. 55)
Design an nfa with no more than five states for the set {$abab^n: n ≥ 0$} $∪$ {$aba^n: n ≥ 0$}. Do you think this can be solved with fewer than three states? (Question 9)
Design an nfa with no more than five states for the set {$abab^n: n ≥ 0$} $∪$ {$aba^n: n ≥ 0$}.Do you think this can be solved with fewer than three states? (Questi...
Naveen Kumar 3
520
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
335
Peter Linz Edition 4 Exercise 2.2 Question 6 (Page No. 55)
For the nfa in following figure, find $δ^*(q_0, 1010)$ and $δ^* (q_1,00)$
For the nfa in following figure, find $δ^*(q_0, 1010)$ and $δ^* (q_1,00)$
Naveen Kumar 3
220
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
336
Peter Linz Edition 4 Exercise 2.2 Question 5 (Page No. 55)
In following figure, find $δ^* (q_0, a)$ and $δ^* ( q_1,λ)$
In following figure, find $δ^* (q_0, a)$ and $δ^* ( q_1,λ)$
Naveen Kumar 3
214
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
337
Peter Linz Edition 4 Exercise 2.2 Question 4 (Page No. 55)
In following figure, find $δ^* (q_0,1011)$ and $δ^* (q_1,01)$
In following figure, find $δ^* (q_0,1011)$ and $δ^* (q_1,01)$
Naveen Kumar 3
228
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
338
Peter Linz Edition 4 Exercise 2.2 Question 3 (Page No. 55)
Find a dfa that accepts the complement of the language defined by the nfa in figure:
Find a dfa that accepts the complement of the language defined by the nfa in figure:
Naveen Kumar 3
1.2k
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
339
Peter Linz Edition 4 Exercise 2.2 Question 2 (Page No. 55)
Find a dfa that accepts the language defined by the nfa in figure:
Find a dfa that accepts the language defined by the nfa in figure:
Naveen Kumar 3
531
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
0
votes
2
answers
340
Peter Linz Edition 4 Exercise 2.1 Question 25 (Page No. 49)
While the language accepted by a given dfa is unique, there are normally many dfa's that accept a language. Find a dfa with exactly six states that accepts the same language as the dfa in figure:
While the language accepted by a given dfa is unique, there are normally many dfa's that accepta language. Find a dfa with exactly six states that accepts the same langua...
Naveen Kumar 3
533
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
341
Peter Linz Edition 4 Exercise 2.1 Question 23 (Page No. 49)
Let $G_M$ be the transition graph for some dfa $M$. Prove the following: (a) If $L (M)$ is infinite, then $G_M$ must have at least one cycle for which there is a path from the initial vertex to some vertex in the cycle and a path from some vertex in the cycle to some final vertex. (b) If $L (M)$ is finite, then no such cycle exists.
Let $G_M$ be the transition graph for some dfa $M$. Prove the following:(a) If $L (M)$ is infinite, then $G_M$ must have at least one cycle for which there is a path from...
Naveen Kumar 3
600
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
342
Peter Linz Edition 4 Exercise 2.1 Question 22 (Page No. 49)
Let, $L$= {$awa: w ∈ $ {$a,b$}* }. Show that $L$* is regular.
Let, $L$= {$awa: w ∈ $ {$a,b$}* }.Show that $L$* is regular.
Naveen Kumar 3
360
views
Naveen Kumar 3
asked
Mar 22, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
0
votes
1
answer
343
Peter Linz Edition 4 Exercise 2.1 Question 20 (Page No. 48)
Let $L$ be the language accepted by the automaton in the following figure. Find a DFA that accepts $L^2$.
Let $L$ be the language accepted by the automaton in the following figure. Find a DFA that accepts $L^2$.
Naveen Kumar 3
467
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
1
answer
344
Peter Linz Edition 4 Exercise 2.1 Question 19 (Page No. 48)
Show that $δ^*(q,wv)=δ^*(δ^*(q,w),v)$ for all $w,v ∈ Σ^*$ . (symbols have standard meaning)
Show that $δ^*(q,wv)=δ^*(δ^*(q,w),v)$for all $w,v ∈ Σ^*$ .(symbols have standard meaning)
Naveen Kumar 3
374
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
1
answer
345
Peter Linz Edition 4 Exercise 2.1 Question 18 (Page No. 48)
Show that if $L$ is regular, so is $L$ $∪$ {$a$}, for all $a∈Σ$.
Show that if $L$ is regular, so is $L$ $∪$ {$a$}, for all $a∈Σ$.
Naveen Kumar 3
401
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
1
votes
2
answers
346
Peter Linz Edition 4 Exercise 2.1 Question 17 (Page No. 48)
Show that if $L$ is regular, so is $L -$ {$λ$} .
Show that if $L$ is regular, so is $L -$ {$λ$} .
Naveen Kumar 3
509
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
0
votes
1
answer
347
Peter Linz Edition 4 Exercise 2.1 Question 16 (Page No. 48)
Show that the set of all real numbers in $C$ is a regular language.
Show that the set of all real numbers in $C$ is a regular language.
Naveen Kumar 3
901
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
348
Peter Linz Edition 4 Exercise 2.1 Question 15 (Page No. 48)
Show that the language $L =$ {$a^n: n$ is a multiple of $3$, but not a multiple of $5$} is regular.
Show that the language $L =$ {$a^n: n$ is a multiple of $3$, but not a multiple of $5$} is regular.
Naveen Kumar 3
331
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
0
votes
1
answer
349
Peter Linz Edition 4 Exercise 2.1 Question 14 (Page No. 48)
Show that the language L= {$a^n: n$ is either a multiple of $3$ or a multiple of $5$} is regular.
Show that the language L= {$a^n: n$ is either a multiple of $3$ or a multiple of $5$} is regular.
Naveen Kumar 3
422
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
1
votes
1
answer
350
Peter Linz Edition 4 Exercise 2.1 Question 13 (Page No. 48)
Show that the language $L= $ {$a^n: n ≥ 0,n ≠ 4$} is regular.
Show that the language $L= $ {$a^n: n ≥ 0,n ≠ 4$} is regular.
Naveen Kumar 3
365
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
regular-language
+
–
0
votes
1
answer
351
Peter Linz Edition 4 Exercise 2.1 Question 12 (Page No. 48)
Show that $L=$ {$a^n: n ≥4$} is regular.
Show that $L=$ {$a^n: n ≥4$} is regular.
Naveen Kumar 3
360
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
0
votes
2
answers
352
Peter Linz Edition 4 Exercise 2.1 Question 11 (Page No. 48)
Show that the language $L=$ {$vwv: v, w ∈$ {$a,b$}*$, |v|= 2$} is regular.
Show that the language $L=$ {$vwv: v, w ∈$ {$a,b$}*$, |v|= 2$} is regular.
Naveen Kumar 3
464
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
0
votes
0
answers
353
Peter Linz Edition 4 Exercise 2.1 Question 10 (Page No. 48)
Construct a dfa that accepts strings on {$0,1$} if and only if the value of the string, interpreted as a binary representation of an integer, is zero modulo five. For example, $0101$ and $1111$, representing the integers $5$ and $15$, respectively, are to be accepted.
Construct a dfa that accepts strings on {$0,1$} if and only if the value of the string, interpreted asa binary representation of an integer, is zero modulo five. For exam...
Naveen Kumar 3
762
views
Naveen Kumar 3
asked
Mar 20, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
+
–
0
votes
0
answers
354
Peter Linz Edition 4 Exercise 2.1 Question 8 (Page No. 47)
A run in a string is a substring of length at least two, as long as possible and consisting entirely of the same symbol. For instance, the string $abbbaab$ contains a run of $b$'s of length three and a run of $a$'s of length two. Find dfa' ... $L$= {$w$ : there are exactly two runs of $a$'s of length 3}.
A run in a string is a substring of length at least two, as long as possible and consisting entirelyof the same symbol. For instance, the string $abbbaab$ contains a run ...
Naveen Kumar 3
1.6k
views
Naveen Kumar 3
asked
Mar 19, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
+
–
4
votes
6
answers
355
Peter Linz Edition 4 Exercise 2.1 Question 6 (Page No. 47)
With $Σ = \{a,b\},$ give a DFA for $L = \{w_1aw_2: |w_1|\geq 3, |w_2|\leq 5\}.$
With $Σ = \{a,b\},$ give a DFA for $L = \{w_1aw_2: |w_1|\geq 3, |w_2|\leq 5\}.$
Naveen Kumar 3
9.7k
views
Naveen Kumar 3
asked
Mar 19, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
+
–
4
votes
1
answer
356
Peter Linz Edition 4 Exercise 2.1 Question 5 (Page No. 47)
Give dfa's for the languages $L= \{ab^5wb^2 : w ∈ \{a,b\}^* \}$ $L= \{ab^na^m : n ≥ 2 , m ≥3\}$ $L = \{w_1abw_2 : w_1 ∈ \{a,b\}^*,w_2 ∈ \{a,b\}^* \}$
Give dfa's for the languages$L= \{ab^5wb^2 : w ∈ \{a,b\}^* \}$$L= \{ab^na^m : n ≥ 2 , m ≥3\}$ $L = \{w_1abw_2 : w_1 ∈ \{a,b\}^*,w_2 ∈ \{a,b\}^* \}$
Naveen Kumar 3
4.4k
views
Naveen Kumar 3
asked
Mar 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
0
votes
1
answer
357
Peter Linz Edition 4 Exercise 2.1 Question 3 (Page No. 47)
$L$ = {$awa : w ∈$ {$a,b$}* } Show that if we change the following figure, making $q_3$ a nonfinal state and making $q_0, q_1,q_2$ final states, the resulting dfa accepts $\bar{L}$
$L$ = {$awa : w ∈$ {$a,b$}* }Show that if we change the following figure, making $q_3$ a nonfinal state and making $q_0, q_1,q_2$ final states, theresulting dfa accepts...
Naveen Kumar 3
876
views
Naveen Kumar 3
asked
Mar 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
2
votes
1
answer
358
Peter Linz Edition 4 Exercise 2.1 Question 2 (Page No. 47)
For $Σ$= {$a,b$}, construct dfa's that accept the sets consisting of (a) all strings with exactly one $a$, (b) all strings with at least one $a$, (c) all strings with no more than three $a$'s
For $Σ$= {$a,b$}, construct dfa's that accept the sets consisting of(a) all strings with exactly one $a$,(b) all strings with at least one $a$,(c) all strings with no mo...
Naveen Kumar 3
4.1k
views
Naveen Kumar 3
asked
Mar 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
0
votes
1
answer
359
Peter Linz Edition 4 Exercise 2.1 Question 1 (Page No. 47)
Which of the strings 0001, 01001, 0000110 are accepted by the dfa
Which of the strings 0001, 01001, 0000110 are accepted by the dfa
Naveen Kumar 3
1.8k
views
Naveen Kumar 3
asked
Mar 19, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
1
votes
0
answers
360
Peter Linz Edition 4 Exercise 1.2 Question 7 (Page No. 28)
Are there languages for which $(L^c)^*=(L^*)^c$
Are there languages for which $(L^c)^*=(L^*)^c$
Naveen Kumar 3
259
views
Naveen Kumar 3
asked
Mar 17, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
finite-automata
+
–
Page:
« prev
1
...
7
8
9
10
11
12
13
14
15
16
17
...
35
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register