Creating a Push Down Automaton from a Grammar

135 Views Asked by At

I have the following grammar, but I'm not sure what exactly it is that it does:

$\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p \end{align}$

How can I go about converting it to a Push Down Automata?

1

There are 1 best solutions below

0
On BEST ANSWER

There is an algorithm for converting a context free grammar to pushdown automaton. It only has one state and the stack symbols are $\{terminals\}\cup\{nonterminals\}$ see for example:

http://www.cs.uiuc.edu/class/fa05/cs475/Lectures/new/bwlec12.pdf

(Don't really know if that is good source, I just googled and glanced at it, (where I learned this stuff isn't in English :D)

Looking at this grammar, it seems to generate logical statements. The symbols are $\vee =$ or, $\wedge =$ and, $\thicksim$ $= $ no and $p$ is a statement.

By these grammar rules, way you can form a statement is by connecting two statements with an $\vee$ or with an $\wedge$. Also the statements $p$ and $\thicksim p$ are ok by themselves.