Cosc 3106 - make a dtm to reverse the input word assume the

Question

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 L_CF.

Question 3) True or False:

i) __L_REG = L_NPDA (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) __L_DTM = L_REC (i.e., the set of languages accepted by Turing machines is the decidable languages.)

iv) __L_NFA ⊃ L_DFA (i.e, the set of languages accepted by deterministic finite automata is a proper subset of the languages accepted by nondeterministic finite automata.)

v) L_DFDA = L_CF (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 = {a^Pb^qc^r |p < q < r} is not context-free.

Hint: You will need to use two values of i.