LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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.