FOR FREE MATERIALS

Example: 

L = ${\mathbf{\omega \omega }}^{\mathbf{R}}$

Consider a language, 

Design the corresponding Push Down Automata (PDA).

You should know:

Before seeing the solution please follow the previous chapter to clear the concept Identification of language Example 2.

Solution:

This given language is an infinite length of palindrome string checking and it is Non deterministic Context Free Language (NCFL) because it creates multiple copies of the stack to check string is accepted or not. 

Total description and detailed analysis of this language are explained here chapter (Identification of language Example 2).

Because this is NCFL we design a corresponding NPDA for it.

First we write the transition functions of NPDA:

Corresponding NPDA:

Here ${\mathbf{q}}_{\mathbf{1}}$ state creates multiple copies of machines. From ${\mathbf{q}}_{\mathbf{1}}$ we start pop from stack assuming that original string is already into stack and rest of the palindrome string is in input tape.

Example:

Here move has multiple choices that are why it is NCFL and machine is NPDA.