(1) Give a non-deterministic finite state automaton with 3 states that accepts the following language.
(2) Show the minimal deterministic finite state automaton that accepts the language given in question (1).
(3) Prove that the following language over is not regular. You may use the pumping lemma for regular languages.
Here, denotes the reverse of . For example, .
(4) Is the language in question (3) a context-free language? If it is, construct a context-free grammar that generates . If not, prove that is not a context-free language.
To construct the minimal deterministic finite state automaton (DFA) for the language , we can use the subset construction method to convert the NFA to a DFA.
We can represent the NFA as a DFA with the following states:
This DFA is minimal and accepts the language .
The transition table for the DFA is as follows:
So we can construct the minimal DFA as follows:
States:
Alphabet:
Start state:
Accept state:
Transition function:
The state diagram for the minimal DFA is as follows:
If is a regular language, then there exists a pumping length such that any string with can be split into three parts satisfying the following conditions:
for all
Let , and consider the string . According to the pumping lemma, can be decomposed into such that the conditions are met.
Let , , where and .
If we pump , the resulting string is .
This string is not in because it does not match the form where . Thus, is not a regular language.