edited by
8,358 views
1 votes
1 votes
Consider the set of strings on {$0,1$} defined by the requirements below. For each, construct an
accepting dfa.
(a) Every $00$ is followed immediately by a $1$. For example, the strings $101, 0010, 0010011001$
     are in the language, but $0001$ and $00100$ are not.
(b) All strings containing $00$ but not $000$.
(c) The leftmost symbol differs from the rightmost one.
(d) Every substring of four symbols has at most two $0$’s. For example, $001110$ and $011001$ are
     in the language, but $10010$ is not since one of its substrings, $0010$, contains three zeros.
(e) All strings of length five or more in which the fourth symbol from the right end is different
     from the leftmost symbol.
(f) All strings in which the leftmost two symbols and the rightmost two symbols are identical.
(g) All strings of length four or greater in which the leftmost three symbols are the same, but
     different from the rightmost symbol.
edited by

1 Answer

7 votes
7 votes

Language over alphabet {0,1}= {every 00 is followed immediately by 1}

DFA:

 

edited by

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2