What are the differences between the computational power of deterministic and non-deterministic stack automata?

Question

There is computational power difference between a deterministic stack automaton and a non-deterministic automaton?

Answer 1

Yeah, there’s a difference between the two. And she’s brutal. Nondeterministic stack automata can solve much more context-free languages than deterministic ones.

I would point out that this goes against other automata, where the non-deterministic Turing machine does not provide computational power beyond that which deterministic can provide, as well as in the nondeterministic finite state machinedeterministic can be transformed into deterministic without loss of computational power.

The set of languages recognized by deterministic pushdown automata is a subset of the set of languages recognized by non-deterministic pushdown automata.

For example, the language composed of every parenthesis needs to be closed in opening order is deterministic. For example, using only square and curved parentheses, the grammar would be:

S --> '(' S ')'
S --> '[' S ']'
S --> '(' ')'
S --> '[' ']'

Now, for palindromes, this doesn’t happen. Take a simple palindrome, composed only of a and b:

S --> 'a' S 'a'
S --> 'b' S 'b'
S --> 'a' 'a'
S --> 'b' 'b'
S --> 'a'
S --> 'b'

How does the automaton distinguish whether it should consider a terminal a as being the beginning of the creation of a pair or the end? For example, the following words are ambiguous:

aabaa
aabababaa

It is impossible for a deterministic stack automaton to determine whether the a after the b should be to start a new pair or if he marries the a previous.