| Abstrakt: | We study descriptional complexity of push down automata recognizing regular languages and
context free languages. We presented the transformation for any finite state automaton A using
n states and given a number of stack symbols p, which reduces the number of states to ⌈ n/p ⌉. We
analyzed descriptional complexity of PDA on the two sequences of regular languages L_1[n]
and L_2[n]. An FSA requires at least n states to accept L_1[n] and L_2[n]. We have shown that
for any n two stack symbols and one state are sufficient for PDA to accept the language L_2[n].
In the other hand, PDA using one state requires at least n stack symbols to accept L_1[n]. Then,
we defined partial ordering on the state and the number of stack complexity measures and
show that there does not exist any function, which combines these measures in such a way that
it maintains complexity from one minimal automaton to another one. Based on these results,
we define two subclasses of push down automata, one state PDA and two stack symbols PDA.
In these subclasses, we have shown tight bounds for one state PDA subclass and upper bounds
for two stack symbols PDA subclass. Finally, we study the costs of operation in these two
subclasses. In particular, we considered union, concatenation and Klenee-Star.
|
|---|