Question

w does not contain Question 2 Consider the following language over the alphabet = {a,b}: L = {w the substring aa} 1. What is I, the complement of L? 2. Write a regular expression for L. 3. Write a regular expression for L. 4. Design a DFA for I. 5. Modify the DFA for I to make it a DFA for L.

please I need it urgent thanks. subject programming language and compilers

Answer 1

L={w| w does not contain the substring aa}

1) L' is the complement of language L. L' can be stated as {w|w contains the substring aa}.

2) The regular expression for the language L={w| w does not contain the substring aa} will be (b+ab)*($\epsilon$+a). We can think of this as to avoid 'aa' in the string every a should be followed by b or there can be as many as b's possible.

3) The regular expression of L' ={w|w contains the substring aa} will be (a+b)*aa(a+b)*.

4) The DFA for L' is shown below:-

ab

5) DFA from L' to L can be easily made by making the complement DFA of L' i.e. by making the non-final states as final states and final states as non-final states.