February 12, 2010

embedded push down automata and parsing MCS languages

I was working on coming out with a solution for parsing the following language using an embedded push down automata, because of the presence of three distinct terminals, it is pretty obvious that a simple push down automata cannot be used.
a^nb^nc^n
The main feature where an embedded PDA varies from a simple PDA is that, it has a stack where multiple stacks can be pushed. New stacks can be pushed above or below the current stack, while symbols can be pushed and popped from the current stack, symbols can only be pushed into stacks other than the current one. This effectively means that in a simple PDA when we perform a POP operation, the information is deleted from the PDA stack, where as in an embedded PDA, when we perform a POP information, the information can be either completely removed from the embedded PDA or be pushed into another stack above or below the current stack. This allows an embedded PDA to parse languages such as the above. The solution for parsing the above language is simple and can be visualized as a simple PDA for the a^nb^n part, but instead of popping out the a's when a b is encountered in the input string, we push the symbol to another stack, the symbols are finally popped out from the system when a corresponding c is encountered.