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


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.

Request for Solution File

Ask an Expert for Answer!!
Theory of Computation: Cosc 3106 - make a dtm to reverse the input word assume the
Reference No:- TGS02724338

Expected delivery within 24 Hours