S- >aSb/A

A-> aA/epsilon

so it has a conflict first of S

?? may be

The Gateway to Computer Science Excellence

+2 votes

For which of the following languages a LL(1) grammar does not exist?

- $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$

- $\{ a^n b^m \mid m,n \geq 0 \}$

- $\{a^ib^j\mid i\geq j\}$

- $\{a^ib^j\mid i= j\}$

0

@Uqxkqc Can you please provide the grammar for Option A?

I got like :

$S \rightarrow A/B$

$A \rightarrow aAb/ab$

$B \rightarrow aBb/aob$

Is this right?

0

If its so then aren't the First sets of A not disjoint? "a" is common in them. They how can it be LL(1)..?

+2

In exam, it is very tough to write grammars for all the languages and then check ambiguity and then remove left recursion and non-determinism and find first and follow in just 3 minutes.. Can anyone please tell, Is there any shortcut to test LL(1) by just seeing the languages?

+1 vote

Best answer

An $LL(1)$ grammar has the following properties

- It should
**NOT**be ambiguous - It should
**NOT**have common prefix problem.(it should be left factored) - It should
**NOT**have left recursion.

The $LL(1)$ grammar for the given languages are as follows :-

Option $A.$

$\{a^n o b^n \mid n \geq 1\} \cup \{ a^n b^{n} \mid n \geq 1 \}$

$S \rightarrow aAb$

$A \rightarrow aAb| \epsilon | o$

Option $B.$

$\{ a^n b^m \mid m,n \geq 0 \}$

$S \rightarrow AB | \epsilon$

$A \rightarrow aA' $

$A' \rightarrow \epsilon | A $

$B \rightarrow bB' $

$A' \rightarrow \epsilon | B $

Option $C.$

$\{a^ib^j\mid i\geq j\}$

$S \rightarrow aS'$

$S' \rightarrow Sb | Ab$ ( Here $FIRST(S) \cap FIRST(A) \neq \phi $ )

$A \rightarrow aA' $

$A' \rightarrow \epsilon | A$

So this is $NOT$ a $LL(1)$ grammar.

Option $D.$

$\{a^ib^j\mid i= j\}$

if $i,j \geq 0 $

$S \rightarrow \epsilon |aSb$

if $i,j >0 $

$S \rightarrow aS'$

$S' \rightarrow b|Sb$

$\therefore$ For option $C$ we can't generate $LL(1)$ grammar.

0

It should

NOThave non-determinism

What does non-determinism mean for a grammar?

Rest part of the answer is fine though why C does not have ant LL(1) grammar can have some reasoning.

0

I updated my answer.

**non-determinism** means that a grammar should not be like $A -> \alpha \beta_1 | \alpha \beta_2 $ type of productions...It will get confuse which production to use. This problem is solved using left factoring.

I think we can't directly look at a DCFL language and give a reason that it can't be LL(1) language. We have to write the grammar for the given language and after writing the grammar , we should try to make it non-ambiguous, left factored and non-left recursive.

if we succeed in doing this then the grammar that we get is a LL(1) grammar else if we are not able to follow any one of the constraints then it is not LL(1).

+1

Well, thats not called non-determinism for grammar though the intention is correct.

And like a language can be inherently ambiguous - we can write an ambiguous grammar and try to make ti unambiguous - we can say from the language itself if it is not LL(1). That is why this question was made. Intuitive reasoning you already told as part of the given grammar.

And like a language can be inherently ambiguous - we can write an ambiguous grammar and try to make ti unambiguous - we can say from the language itself if it is not LL(1). That is why this question was made. Intuitive reasoning you already told as part of the given grammar.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,394 answers

198,594 comments

105,445 users