Consider the following context free languages: L₁ = {0^i 1^j 2^k | i+j = k} L₂ = {0^i 1^j 2^k | i = j or j = k} L₃ = {0^i 1^j | i = 2j+1} Which of the following option is true? A)L₁, L₂ and L₃ can be recognized by Deterministic Push down automata B)L₁, L₂ can be recognized by Deterministic Push down automata C)L₁, L₃ can be recognized by Deterministic Push down automata D)None of the above

Question

Quizplus · Accepted Answer

L₁ and L₃ can be recognized by deterministic pushdown automata (DPDA) because they have a specific pattern that allows a DPDA to track the relationship between the numbers of 0s, 1s, and 2s (for L₁) and between the numbers of 0s and 1s (for L₃) deterministically. L₂, however, involves a non-deterministic choice (i = j or j = k) which cannot be resolved by a DPDA.

Consider the Following Context Free Languages