Question

Give reasons why one might conjecture that the following language is not deterministic.

L = {aⁿb^mc^k: n = m or m = k}.

Answer 1

Given language, L = {aⁿb^mc^k: n = m or m = k}.

Clearly, for two conditions, the language can be accepted by a PDA (push down automata). The first condition is equality of the number of a's and number of b's in the string and the second condition is the equality of the number of b's and number of c's in the string. Thus, if a PDA is generated for such language, there must be two different final states for two different conditions. Thus, two choice are there in the PDA. In the first case, 'a' will be pushed in the stack and 'b' will cause pop from the stack (and skip 'c') to check equivalence and in second case, (skip 'a') 'b' will be pushed in the stack and 'c' will cause pop from the stack to check equivalence.

So the PDA will not deterministic. Means, one string that is accepted by path 1 will not be accepted by path 2 (towards final state) and vice versa. Thus, there is a conflict in the acceptance of the string and thus the given language is not deterministic.