Question

Let sigma = {a, b, c}. Draw the transition graph of a npda that accepts the following language: L = {c(ab)^n a^m c^n: n greaterthanorequalto 1, m greaterthanorequalto 0} Write the sequence of moves done by the npda when the input sequence is w = cabc. Is the string w accepted?

Answer 1

Refer to the image below for the NPDA of the language given in the question:

a, 2,2 a, 2,2 C, z,z a,z,x NOTE: The symbol є is used to denote null symbol in the above diagram. In your book, it may have been shown using λ symbol. So, please take that into account. For w = cabc , the following sequence of moves is done by the NPDA: Current state Input Symbol Stack Symbol Next state Stack on transition 1o Th 72 Th 1 s (ACCEPT)

The sequence of moves for the given string can be seen in the table present in the above image. So, the string is accepted by the NPDA.