Question

Whether the PDA accepts all the languages that have been accepted by the FA? Yes or No, explain in either case with an example.


Whether the FA accepts all the languages that have been accepted by the PDA? Yes or No, explain in either case with an example.

Answer 1

CpSc 8390 — Goddard — Fall15Supplemental Questions1  Finite AutomataA1:  For the following, build a deterministic FA. The alphabet is{0,1}.  The empty string isnot in the language.  If the string starts with a0, then the string has length at least 3.If the string starts with a1, then the last bit must be a0.A2:  Consider the following languageLwith alphabet{0,1,2}.Every string inLstarts with a2, ends with a1, and contains an even number of0’s.For example, both201100201and211are in the language.Give both a DFA and an RE forL.A3:  LetMbe the language described as follows.  The alphabet is{0,1}.The empty string is inM.  If a string starts with a0, then it ends with a1.  If a stringstarts with a1, then it does not contain00as a substring.Give both a DFA and an RE forM.A4:  Describe in succinct English what languages the following two FAs accept:01101001111100001111000022222222A5:  Give an RE for the set of all binary strings that do not contain101as a substring.

A6:  Consider the following FA.0101010101010101(a) Which 3-bit strings does it accept?(b) Describe in English the language accepted by the machine.A7:  Consider the following DFA.ABC011001(a) List all 4-bit strings accepted by the machine.(b) Give an RE for this language of the machine.(c)  Describe  in  English  the  language  of  this  machine.   (Hint:  consider  the  strings  asbinary.)A8:  LetJbe the language given by the RE (a+ba)∗.(a) List all strings of length 4 inJ.(b) Give an NFA that acceptsJ.