Made Easy Test Series

Question

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....???!!!

Comments

every dfa contain dead state ? No na.

---

every dfa is not having dead state,only some of them.

---

Just Consider Initial State I_0, 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...?

---

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.

Answer 1

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.

Answer 2

There is no clubing of states.LALR(1) is same as CLR(1).You please check once!!

Comments

clubbing of states means to combine those states those are differ by only lookahead symbol