The Gateway to Computer Science Excellence
+1 vote
Consider the following CFG.

S $\rightarrow$aAb|aBc|bAd|bBe

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 by (237 points)
retagged by | 236 views
every dfa contain dead state ? No na.
every dfa is not having dead state,only some of them.

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

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.
by (159 points)
0 votes
There is no clubing of states.LALR(1) is same as CLR(1).You please check once!!
by Boss (10.8k points)
clubbing of states means to combine those states those are differ by only lookahead symbol
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,309 answers
105,023 users