PDA Examples

Example:

 

Consider a language, 

 

Let's take an input: 

 

 

 

Because of the given language is DCFL and machine is DPDA so, there will be only one move possible for one input.

To design the DPDA for this given language we should write all the transition functions which can help us to design the machine properly.

 

 

 

 

 

 

DPDA: 

 

Accepted by final and empty stack 

Example:  

Consider a language,

 

 

Design the corresponding Push Down Automata (PDA). 

 

Let's take an input: 

 

 

 

Corresponding DPDA:

 

Let's take an input: 

Consider a language, 

 

Design the corresponding Push Down Automata (PDA).

 

Example: 

 

 

 

Corresponding DPDA:

 

Example: 

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA).

Let's take an input: 

 

(This type of strings are accepted)

 

 

 

 

 

Corresponding DPDA:

 

 

Example: 

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA)

 

Let's take an input:  

(This type of strings are accepted)

 

Corresponding DPDA:

 

 

Example: 

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA).

Let's take an input: 

 

(This type of strings are accepted)

 

Corresponding DPDA:

 

 

Example:  

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA).

Let's take an input: 

 

 

Answer:  Here we push two ‘a’ for a single input ‘b’.

 

 

 

Corresponding DPDA:

 

Example: 

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA).

Let's take an input 

 

 

Corresponding DPDA:

 

Example: 

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA).

 

Let's take an input, ω = a a b b b b a b a a. Here number of a and b is same.

 

 

Corresponding DPDA:

 

Example: 

Consider a language, 

 

 

Design the corresponding Push Down Automata (PDA).

 

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

 

First we write the transition functions of NPDA:

 

 

It creates multiple copies of the machine.

 

Corresponding NPDA:

 

Example:

 

 

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