15,722 views
9 votes
9 votes

Each of the following languages is the complement of a simpler language. In each part, construct a $\text{DFA}$ for the simpler language, then use it to give the state diagram of a $\text{DFA}$ for the language given. In all parts, $Σ = {a, b}.$

  1. $\text{\{w| w does not contain the substring ab\}}$
  2. $\text{\{w| w does not contain the substring baba\}}$
  3. $\text{\{w| w contains neither the substrings ab nor ba\}}$
  4. $\text{\{w| w is any string not in a*b*\}}$
  5. $\text{\{w| w is any string not in}$ $(ab^{+})^{*}\}$
  6. $\text{\{w| w is any string not in}$  $a^{*}\cup b^{*}\}$ 
  7. $\text{\{w| w is any string that doesn’t contain exactly two a’s\}}$
  8. $\text{\{w| w is any string except a and b\}}$

1 Answer

5 votes
5 votes

a. L=w contains sub-string ab

     complement of L=w does not contains sub-string ab

b. L=w contains sub-string baba

     complement of L=w doesn not contains sub-string baba

 

c. L=w contains neither ba nor ab

d. L=w in a*b*

L=w not in a*b*

e. L=w in (ab+)*

L=w not in (ab+)*

f. L=w in a*+b*

L=w not in a*+b*

g. L=w has exactly 2 a's

L=w doesn't have 2 a's

h. L=w is ant string except 'a' and 'b'

edited by

Related questions

0 votes
0 votes
1 answer
1
admin asked Apr 21, 2019
4,539 views
Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA’s}$ recognizing the union of the languages described in$L_{1}=\text{...