Register

Linear Ambiguous Context Free Grammar

• edited by
3,143 views
1 1 vote
Please post few examples of Linear Ambiguous Context Free Grammar.

It would be helpful if you post grammars for famous languages.

1 Answer

0 0 votes
a^i b^j c^k such that i=j or j=k

this is linear and inherently ambiguous language

more popularly its known as

a^m b^m c^n $\cup$ a^m b^n c^n such that m,n>=1

PROVED BY OGDEN (Ogden's lemma)
Voting & Accepting an answer helps improve the community
← Previous · Binary Search TreeNext → · IIT ROORKEE
← Previous in category · Peter linz exercise ...Next in category → · Self_doubt
Position:
Show:

Related questions

0 0 votes
2 2 answers
682
682 views
moe12leb asked Jan 21, 2023
682 views
context free grammar
what is the langauge generated by this grammar ?S >aS | aSbS | ε what is the language
2 2 votes
2 2 answers
1.5k
1.5k views
Sambhrant Maurya asked Oct 18, 2018
1,495 views
Context Free Grammar
Consider the following CFG 'G'S aA/bSS/SSA aAb/bAa/AA/εThe language generated by G is:a)Set of all strings with atleast one 'a'b)Set of all strings with atleast two a's...
0 0 votes
1 answers 1 answer
762
762 views
Srinivas Rao asked Apr 4, 2017
762 views
context free grammar
Do the following productions mean the sameBb->bb and B->bMy doubt is that will the first production be used only when we have b in the follow of B or it can be used in an...
1 1 vote
1 answers 1 answer
1.0k
1.0k views
gabbar asked Mar 25, 2017
1,034 views
context free grammar
Construct context-free grammars to accept the following languages.$$\begin{align*} \large L = \left \{ 0^i1^j2^k \;\; | \;\; i \neq j \;\; or \;\; j \neq k \right \} \end...