Question

UueSLIORS! 1. Find the error in logic in the following statement: We know that a b' is a context-free, not regular language. The class of context-free languages are not closed under complement, so its complement is not context free. But we know that its complement is context-free. 2. We have proved that the regular languages are closed under string reversal. Prove here that the context-free languages are closed under string reversal. 3. Part 1: Find an NFA with 3 states that accept the following language L = {a" : n 2 1} U {f"ok : m 2 0,k 20}. Part 2: Do you believe the language can be accepted by an NFA with less than 3 states? 4. Which of the strings below is accepted by the NFA? a. 000010100110 b. 01001 c. 1011111010 d. 0001011001100 e 0000 f. 01011101101 g. 1011101110000011101 h. 11101111 5. (a) Give a NFA that accepts the language generated by the regular expression (a+ba)(b + ab)+(b+a*b). (b) Convert your NFA to a DFA. 6. Provide a regular expression for the following languages over (cd): a. Nonempty strings in which the first and last symbols are different b. Strings in which the number of d's is even and the number of c's is odd. c. Strings in which the number of c's and d's are either both even or both odd. d. Strings of any length that can only contain the substring cd after the occurrence of de.

Answer 1

1. Class of CFL are not closed under complementation does not mean that if L is CFL then $\bar{L}$ is always not context-free. It could either be context-free or not context-fred.

2. For every CFL L, there is a CFG G such that L(G)= L.

Now L^R i.e. reverse of L can be produced by grammar G' such that G' has all the production rules of G in reverse order. This means that if G has production rule
N na
where
a € {NUV}"
I.e. any combination of terminal and non-terminal, then G' will have rule
N → Reverse(a)

Now G' will produce language which is reverse of language produced by G. Since CFG G' exist for Reverse(L), hence Reverse(L) is context-free.

3. Below is the NFA for it.

Yes this can be accepted by NFA with 2 states as well shown below

4. The regular expression for this NFA is

(0+1)*01(0+011)*11*

Here string ending with 1 could only be accepted by this NFA with some other property. Here string b will only be accepted by this NFA.

Please post 2 questions 5 and 6 separately.