Register

Recent questions tagged peter-linz-edition4

1 votes
1 answer
243
Peter Linz Edition 4 Exercise 3.1 Question 18 (Page No. 76)
Find regular expressions for the following languages on {$a, b$}. (a) $L =$ {$w : |w|$ mod $3 = 0$}. (b) $L =$ {$w : n_a (w)$ mod $3 = 0$}. (c) $L =$ {$w : n_a (w)$ mod $5 > 0$}.
Find regular expressions for the following languages on {$a, b$}.(a) $L =$ {$w : |w|$ mod $3 = 0$}.(b) $L =$ {$w : n_a (w)$ mod $3 = 0$}.(c) $L =$ {$w : n_a (w)$ mod $5 ...
User Avatar
0 votes
0 answers
254
Peter Linz Edition 4 Exercise 3.1 Question 3 (Page No. 75)
Show that $r = (1 + 01)^* (0 + 1^*)$ also denotes the language in $L =$ {$w∈${$0,1$}$^* : w$ has no pair of consecutive zeros}. Find two other equivalent expressions.
Show that $r = (1 + 01)^* (0 + 1^*)$ also denotes the language in $L =$ {$w∈${$0,1$}$^* : w$ has no pair of consecutive zeros}. Find two other equivalent expressions.
User Avatar
0 votes
0 answers
258
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.
User Avatar
0 votes
0 answers
261
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.
User Avatar
2 votes
0 answers
266
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....
User Avatar
1 votes
1 answer
270
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$.
User Avatar
Page: