PDA Examples
Example:
Consider a language,
.png)
Let's take an input:
.png)
.png)
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.
.png)
.png)
.png)
.png)
.png)
DPDA:
.png)
Accepted by final and empty stack
.png)
Example:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA).
Let's take an input:
.png)
.png)
Corresponding DPDA:
.png)
Let's take an input:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA).
Example:
.png)
.png)
Corresponding DPDA:
.png)
Example:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA).
Let's take an input:
.png)
.png)
.png)
.png)
.png)
Corresponding DPDA:
.png)
.png)
Example:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA)
Let's take an input:
.png)
Corresponding DPDA:
.png)
.png)
Example:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA).
Let's take an input:
.png)
Corresponding DPDA:
.png)
.png)
Example:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA).
Let's take an input:
.png)
Answer: Here we push two βaβ for a single input βbβ.
.png)
.png)
.png)
Corresponding DPDA:
.png)
Example:
Consider a language,
.png)
Design the corresponding Push Down Automata (PDA).
Let's take an input .png)
.png)
Corresponding DPDA:
.png)
Example:
Consider a language,
.png)
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.
.png)
Corresponding DPDA:
.png)
Example:
Consider a language,
.png)
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:
.png)
.png)
.png)
.png)
.png)
.png)
Corresponding NPDA:
.png)
Example:
.png)
Here move has multiple choices that are why it is NCFL and machine is NPDA.
Labels: Automata, TAFL Unit-4
Discussion & Queries (<$I18NNumComments$>):
<$CommentPager$>
- <$I18NAtCommentTimeWithPermalink$>, <$I18NCommentAuthorSaid$>
<$CommentPager$>
<$BlogCommentBody$>
<$BlogCommentDeleteIcon$>