Consider the following languages : L = {anbncm} ∪ {anbmcm}, n, m ≥ 0 1 L = {wwR ∣ w ∈ {a, b}*} 2 Where R represents reversible operation. Which one of the following is (are) inherently ambiguous language(s)? L
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. only 1 L
Explanation
{aⁿbⁿcᵐ} ∪ {aⁿbᵐcᵐ} is the classic inherently ambiguous CFL (strings aⁿbⁿcⁿ have two derivations in every grammar). wwᴿ has an unambiguous grammar S → aSa | bSb | λ.
More Theory of Computation and Compilers questions
- Let G=(V, T, S, P) be any context-free grammar λ without any -productions or unit productions. Let K be the maximum number of symbols on th…
- Consider the following language families : L ≡ The context - free languages 1 L ≡ The context - sensitive languages 2 L 3 ≡ The recursively…
- Consider the following statements : S 1 : These exists no algorithm for deciding if any M M two Turing machines 1 and 2 accept the same lan…
- Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}; C = {00, 001, 1000} and D = {0, 11, 011}. Which pairs have a Post correspondence…
- Which data structure is used by the compiler for managing variables and their attributes?
- On translating the expression given below into quadruple representation, how many operations are required? (i*j)+(e+f)*(a*b+c)