Home /
Expert Answers /
Computer Science /
6-10-pts-let-a-give-a-dfa-re-cfg-pda-and-a-turing-machine-that-decides-the-language-l-pa926
(Solved): 6. (10 pts.) Let ={a}. Give a DFA/RE, CFG/PDA, and a Turing machine that decides the language L= ...
6. (10 pts.) Let . Give a DFA/RE, CFG/PDA, and a Turing machine that decides the language , if it exists. If any of the three does not exist, prove in detail why it does not exist. Is ? Is ?(Justify your answers.)
Expert Answer
DFA/RE: The language L={a^2n} over ?={a} can be recognized by the following DFA, which has two states: q0 and q1. The start state is q0 and the only accepting state is q1. From the start state, if we see two consecutive a's, we move to the accepting state q1. Otherwise, we stay in the start state.DFA for L={a^2n}: The regular expression for L can be written as (aa)*.