Reference no: EM132093975

Questions -

1) Make an NPDA to accept L = {w|w ∈ {a, b}* and w contains an equal number of a's and b's}.

2) List the closure properties of L_CF.

closed under:

not closed under:

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_DTNA = 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_DPDA = L_CF (i.e, the set of languages accepted by deterministic pushdown automata is the context-free languages.)

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

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

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.