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 11:47] vkuncak |
visibly_pushdown_languages [2007/06/05 11:20] vkuncak |
||
---|---|---|---|
Line 13: | Line 13: | ||
===== Visibly pushdown automaton ===== | ===== Visibly pushdown automaton ===== | ||
+ | |||
+ | The key restriction compared to nondeterministic pushdown automata is that whether a visibly pushdown automaton will push or pop is determined only by the input symbol. (The automaton can change the state in a non-deterministic way, and can non-deterministically decide what to push.) | ||
A (nondeterministic) visibly pushdown automaton (on finite words) over the pushdown alphabet $(\Sigma_c,\Sigma_r,\Sigma_l)$ is a tuple $M = (Q,Q_{in},\Gamma,\delta,Q_F)$ where | A (nondeterministic) visibly pushdown automaton (on finite words) over the pushdown alphabet $(\Sigma_c,\Sigma_r,\Sigma_l)$ is a tuple $M = (Q,Q_{in},\Gamma,\delta,Q_F)$ where | ||
Line 30: | 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 42: | Line 46: | ||
Solution: not just a set of states, but a summary of relation from initial to final states of 'procedure'. Then update directly the effect of a procedure call on each state. | Solution: not just a set of states, but a summary of relation from initial to final states of 'procedure'. Then update directly the effect of a procedure call on each state. | ||
- | Note: you never store original symbols on the stack. | + | Note: you never store original symbols on the stack (but we store the call input symbol). |
+ | |||
+ | ===== MSOL over strings with matching relation ===== | ||
+ | |||
+ | Thanks to closure properties. | ||
+ | |||
+ | |||
+ | ===== Stack trees ===== | ||
+ | |||
+ | We can associate //injectively// trees with words over pushdown alphabet, then visibly pushdown languages correspond to regular trees. | ||
+ | |||
+ | Can we obtain closure and other properties from properties of tree automata? | ||
+ | |||
+ | ===== Visibly pushdown grammars ===== | ||
===== References ===== | ===== References ===== |