Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
visibly_pushdown_languages [2007/05/31 12:04] vkuncak |
visibly_pushdown_languages [2007/06/05 11:20] vkuncak |
||
---|---|---|---|
Line 32: | Line 32: | ||
Stack always contains $\bot$ as the bottom element. A visibly pushdown automaton never pushes or pops $\bot$. | Stack always contains $\bot$ as the bottom element. A visibly pushdown automaton never pushes or pops $\bot$. | ||
+ | |||
+ | ===== Every context-free language is a 'projection' of some visibly pushdown language ===== | ||
===== Closure properties ===== | ===== Closure properties ===== | ||
Line 50: | Line 52: | ||
Thanks to closure properties. | Thanks to closure properties. | ||
- | ===== Strack trees ===== | + | |
+ | ===== Stack trees ===== | ||
We can associate //injectively// trees with words over pushdown alphabet, then visibly pushdown languages correspond to regular trees. | We can associate //injectively// trees with words over pushdown alphabet, then visibly pushdown languages correspond to regular trees. |