Conversion form of PDA

<< PDA corresponding to CFG

Conversion Form, Joints of the machine >>

Theory of Automata

(CS402)

Theory of Automata

Lecture N0. 40

Reading Material

Introduction to Computer Theory

Chapter 15

Summary

Recap of example of PDA corresponding to CFG, CFG corresponding to PDA. Theorem, HERE state,

Definition of Conversion form, different situations of PDA to be converted into conversion form

Example

Consider the following CFG

S Æ XY

X Æ aX | bX |a

Y Æ Ya | Yb | a

First of all, converting the CFG to be in CNF, introduce the nonterminals A and B as

AÆa

BÆb

The following CFG is in CNF

S Æ XY

X Æ AX | BX |a

Y Æ YA | YB | a

AÆa

BÆb

The PDA corresponding to the above CFG will be

START

PUSH S

POP

PUSH X

PUSH B

PUSH A

PUSH X

PUSH Y

PUSH X

PUSH B

PUSH A

PUSH Y

Theorem

Given a PDA that accepts the language L, there exists a CFG that generates exactly L.

Before the CFG corresponding to the given PDA is determined, the PDA is converted into the standard form

which is called the conversion form.

Before the PDA is converted into conversion form a new state HERE is defined which is placed in the middle of

any edge.

Like READ and POP states, HERE states are also numbered e.g.

123

Theory of Automata

(CS402)

becomes

HERE3

Conversion form of PDA

Definition

A PDA is in conversion form if it fulfills the following conditions:

There is only one ACCEPT state.

There are no REJECT states.

Every READ or HERE is followed immediately by a POP i.e. every edge leading out of any READ or HERE

state goes directly into a POP state.

No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are

any intervening PUSH states (i.e. the POP states must be separated by READs or HEREs).

All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every

edge has only one label.

Even before we get to START, a "bottom of STACK" symbol $ is placed on the STACK. If this symbol is ever

popped in the processing it must be replaced immediately. The STACK is never popped beneath this symbol.

Right before entering ACCEPT this symbol is popped out and left.

The PDA must begin with the sequence

START

POP

PUSH $

HERE

The entire input string must be read before the machine can accept the word.

Different situations of a PDA to be converted into conversion form are discussed as follows

To satisfy condition 3,

becomes

PUSH a

POP

PUSH b

PUSH $

To satisfy condition 4,

POP4

POP5

becomes

POP4

POP5

HERE

To satisfy condition 5

POP1

124

Theory of Automata

(CS402)

becomes

POP2

POP3

To satisfy condition 5

PUSH a

POP

PUSH b

becomes

POP1

PUSH a

POP2

PUSH b

To satisfy condition 6, it is supposed that the STACK is initially in the position shown below

STACK

125

Table of Contents: