how to determine if a context free language is deterministic or nondeterministic in general

1.7k Views Asked by At

how to determine if a context free language is deterministic or nondeterministic in general

to make sure a language is deterministic we can make DPDA for it

how can we make sure of nondeterminism ?

for example for L = { WWR }

how can we say its deterministic or nondeterministic

1

There are 1 best solutions below

0
On

There is no formal, easy-to-apply, definite criterion.

Intuitively, for $\{ww^R: w\in \Sigma^*\}$ the PDA has to know at some point that it is at the center of the word and from now on has to match $w$ against $w^R$. But there is no way of knowing this. Of course, there could always be a way that you just do not see...

On the other hand, the language $\{wcw^R: w\in \{a,b\}^*\}$ is deterministic, because here the center is marked by the unique occurrence of $c$ and thus can be recognized easily.

see also this question.