Register

NIELIT 2021 Dec Scientist A - Section B: 92

• edited by
250 views
0 votes
0 votes

Consider the grammar with nonterminals $\text{N = \{ S, C, S}_{1} \}$ terminals $\text{T = \{ a, b, i, t, e \}}$ With $\text{S}$ as the start symbol, and the following set of rules :

$\text{S} \rightarrow \text{i Ct SS}_{1} | \text{a}$

$\text{S}_{1} \rightarrow \text{eS} | \in $

$\text{C} \rightarrow \text{b}$

The grammar is not $\text{LL}(1)$ because :

  1. It is left recursive
  2. It is right recursive
  3. It is ambiguous
  4. It is not context free
• edited by
User Avatar

1 Answer

0 votes
0 votes

C. It is ambiguous ...

 

A LL(1) grammar doesn't give to multiple entries in a single cell of its parsing table...

It has only single entry in a single cell, hence it should be unambiguous....

 

Option A is wrong.

Grammar is not left recursive. For a grammar to be left recursive a production should be of form A → Ab, where A is a single Non-Terminal and b is any string of grammar symbols....

 

Option B is wrong. Because a right recursive grammar has nothing to do with LL(1)....

 

Option D is wrong. Because the given grammar is clearly a Context Free Grammar.

A grammar is CFG if it has productions of the form A → (V ∪ T) *, where A is a single non-terminal and V is a set of Non-terminals and T is a set of Terminals....

 

Hence Option C should be the correct one. i.e. the grammar is ambiguous. But let's see how the grammar is ambiguous....

If the grammar is ambiguous then it should give multiple entry in a cell while making its parsing table.

And Parse table is made with the aid of two functions: FIRST and FOLLOW....

 

A parsing table of a grammar will not have multiple entries in a cell ( i.e. will be a LL(1) grammar)

if and only if the following conditions hold for each production of the form A → α | β ...

 

1. FIRST (α) ∩ FIRST(β) = φ ...

2. If FIRST (α) contains ' ε ' then FIRST(α) ∩ FOLLOW (A) = φ and vice-versa...

Now,

• For the production,

S → iCtSS1|a, rule 1 is satisfied, because FIRST(iCtSS1) ∩ FIRST(a) = {i} ∩ {a} = φ ...

• For the production,

S1 → eS| ε, rule 1 is satisfied, as FIRST(eS) ∩ FIRST(ε) = {e} ∩ {e} = φ....

 

But here due to ' ε ' in FIRST, we have to check for rule 2....

 

FIRST(eS) ∩ FOLLOW(S1) = {e} ∩ {e, $} ≠ φ....

Hence rule 2 fails in this production rule....

Therefore there will be multiple entries in the parsing table, hence the grammar is ambiguous and not LL(1).…

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
soujanyareddy13 asked Jan 9, 2022
949 views
NIELIT 2021 Dec Scientist A - Section B: 43
Let the predicates $D(x,y)$ mean team $x$ defeated team $y$ and $P(x,y)$ mean team $x$ has played team $y$ ... $ \forall y \exists x (P(x,y) \rightarrow D(x,y))$ $\exists x \forall y (D(x,y) \rightarrow P(x,y))$
Let the predicates $D(x,y)$ mean “team $x$ defeated team $y$” and $P(x,y)$ mean “team $x$ has played team $y$”. The quantified formula for the statement that ther...
User Avatar
0 votes
0 votes
1 answer
2
soujanyareddy13 asked Jan 9, 2022
607 views
NIELIT 2021 Dec Scientist A - Section B: 44
The File Transfer Protocol is built on ______________. data centric architecture service-oriented architecture client server architecture connection-oriented architecture
The File Transfer Protocol is built on ______________.data centric architectureservice-oriented architectureclient server architectureconnection-oriented architecture
User Avatar
0 votes
0 votes
1 answer
3
soujanyareddy13 asked Jan 9, 2022
530 views
NIELIT 2021 Dec Scientist A - Section B: 45
More than one word is put in one cache block to: exploit the temporal locality of reference in a program exploit the spatial locality of reference in a program reduce the miss penalty none of the option
More than one word is put in one cache block to:exploit the temporal locality of reference in a programexploit the spatial locality of reference in a programreduce the mi...
User Avatar
0 votes
0 votes
1 answer
4
soujanyareddy13 asked Jan 9, 2022
456 views
NIELIT 2021 Dec Scientist A - Section B: 46
In $\text{DPSK}$ technique, the technique used to encode bits is : $\text{AMI}$ Differential code Unipolar $\text{RZ}$ format Manchester formate
In $\text{DPSK}$ technique, the technique used to encode bits is :$\text{AMI}$Differential codeUnipolar $\text{RZ}$ formatManchester formate
User Avatar
Link Copied!