Reference no: EM131928863
Question 1) Make an NPDA to accept L = {w|w ∈ {a,b}* and w contains an equal number of a's and b's}.
Question 2) List the closure properties of LCF.
Question 3) True or False:
i) __LREG = LNPDA (i.e., the set of languages accepted by nondeterministic pushdown automata is the regular languages.)
ii) __Given an arbitrary context-free language L, it is possible to make a deterministic Turing machine to accept L.
iii) __LDTM = LREC (i.e., the set of languages accepted by Turing machines is the decidable languages.)
iv) __LNFA ⊃ LDFA (i.e, the set of languages accepted by deterministic finite automata is a proper subset of the languages accepted by nondeterministic finite automata.)
v) LDFDA = LCF (i.e, the set of languages accepted by deterministic pushdown automata is the context-free languages.)
Question 4) Given the following grammar in GNF, make an NPDA to accept the same language.
S -> aXA | bXB | λ
A -> a
B -> b
X -> aXA | bXB |a|b
Question 5) Make a DTM to reverse the input word. Assume the input word is a binary string, that the start of the tape is marked by ⊥, and that the end of the input is marked by the symbol Ω.
Question 6) Prove that the language L = {aPbqcr |p < q < r} is not context-free.
Hint: You will need to use two values of i.