Question - In the lecture 41 ‘s example, we have converted PDA to conversion form and a word ‘aaaabb’ is derived from this conversion form PDA. What are the derivation steps.
Answer -
The PDA converted to conversion form has some specific features that are important to understand first. These features are
The states named START, READ, HERE and ACCEPT are called joints of the machine.
With the help of the conversion form we have been able to achieve that POP state has only one path out of it and the path taking (multiple paths) decisions take place only on the READ state.
The word ‘aaaabb’ is generated as follows from the PDA
START-POP4-PUSH $
This step pops $ and then pushes it to ensure that stack contains $ at the beginning.
READ1-POP6-PUSH $-PUSH a
As first time after reading “a” there is $ at the top of stack so we will follow path segment READ1-POP6-PUSH $-PUSH a
READ1-POP5-PUSH a-PUSH a
Now a is on the top of the stack so we will follow READ1-POP5-PUSH a-PUSH a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP1- HERE-POP2
As we read b on input tape.
READ2-POP1-HERE-POP2
As we read b on input tape.
READ2-POP3-ACCEPT.
As we read ∆ from the input tape