search
Log In
1 vote
605 views
Consider the following CFG.

S $\rightarrow$aAb|aBc|bAd|bBe
A$\rightarrow$g
B$\rightarrow$g

The number of states exist in DFA using LALR (1) construction for the above grammar  ____________??

(Doubt): In CLR(1) it takes 14 states and clubbing two states into one state will take 13 states in LALR(1). The LALR(1) construction takes 13 states for the construction but additional one more dead state is required as we are using DFA....!!! So 14 is the answer, I think.. But answer in Made Easy given as 13 Only.. Explain....???!!!
in Compiler Design
retagged by
605 views
2
every dfa contain dead state ? No na.
0
every dfa is not having dead state,only some of them.
0

Just Consider Initial State I0, from that initial state on input g where does the next state goes.....?

As it is DFA at a particular state, state is defined for each and every input...?

0
In the CLR(1) table on every input symbol it performs either shift action or reduce action.

on particular input it is going to blank symbol,then system understands that is not valid string.and returns error.

2 Answers

1 vote
In LALR(1) minimal states are considered after clubbing the states which are differ only by lookahead symbol. If after clubbing,states are reduced then consider the reduced dfa .No need to consider dead state or anything.
0 votes
There is no clubing of states.LALR(1) is same as CLR(1).You please check once!!
0
clubbing of states means to combine those states those are differ by only lookahead symbol

Related questions

0 votes
0 answers
2
216 views
L1 = {an bm | n ≤ m ≤ 2n} L2 = {an bm│m≠n & m≠2n} Which of the following is true? A. Only L1 is CFG B. Only L2 is CFG C. Both are CFG D. None of them is CFG
asked Jan 26, 2017 in Theory of Computation AmitPatil 216 views
1 vote
2 answers
3
420 views
Consider the following CFG. S → aSa | bSb | a | b | ε For the above CFG, the total number of strings generated whose length is less than or equal to 8 [exclude the empty string] is _____________.
asked Jul 31, 2018 in Theory of Computation himgta 420 views
1 vote
0 answers
4
608 views
$S\rightarrow aA|bAc|dc$ $A\rightarrow d$ Number of states in $CLR\left ( 1 \right )$ parser construction _______________ Is $S\rightarrow d.c|$ $A\rightarrow d.,a$ will be in $1$ state or in $2$ different states??
asked May 15, 2019 in Compiler Design srestha 608 views
...