n

$\backslash$

epsi

$-$

free PDA is a PDA with two modifications:

$$

$$that does not have any

$\backslash$

epsi transitions

$($

having

$\backslash$

epsi for stack actions is OK

$)$

$,$

$$and

$$

$$it can push multiple symbols in one transition

$($

however it can pop at most one symbol per transition

$)$

$.$

That is

$,$

$($

Q

$,$

$\backslash$

Sigma

$,$

$\backslash$

Gamma

$,$

$\backslash$

delta

$,$

$$q

$0$

$$F

$)$

$$is an

$\backslash$

epsi

$-$

free PDA iff it is a PDA with the following modified transition function:

$\backslash$

delta : Q

$\backslash$

times

$\backslash$

Sigma

$\backslash$

times

$\backslash$

Gamma

$\backslash$

epsi

$-$

$>$

$$P

$($

Q

$\backslash$

times

$\backslash$

Gamma

$)$

$.$

Here, P

$($

A

$)$

$$is the powerset of A that contains only finite sets. Note that there are

$2$

$$differences to

$\backslash$

delta :

$1$

$.$

$$The second argument of

$\backslash$

delta cannot be

$\backslash$

epsi

$.$

$2$

$.$

$$

q in Q

$,$

$\backslash$

sigma in

$\backslash$

Sigma

$,$

$\backslash$

gamma in

$\backslash$

Gamma

$\backslash$

epsi

$.$

$\backslash$

delta

$($

q

$,$

$\backslash$

sigma

$,$

$\backslash$

gamma

$)$

$$returns a finite set of pairs made up of a state, and a sequence of symbols

from the stack alphabet

$($

as opposed to a state and a single stack symbol or

$\backslash$

epsi from the definition of a normal

PDA

$)$

$.$

The accepting criterion for

$\backslash$

epsi

$-$

free PDA follow the same form presented for PDA in the lectures.

Prove or disprove: the class of languages

$\backslash$

epsi

$-$

free PDA recognize is the class of context

$-$

free languages. convert a GNF to $\backslash$

epsi

$-$

free PDA