7.5k views

Consider the following two statements:

• P: Every regular grammar is LL(1)
• Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

1. Both P and Q are true

2. P is true and Q is false

3. P is false and Q is true

4. Both P and Q are false

0

Hi, all previous GATE questions are already here- you can use the above google searchbar or use Prev Exams link in navbar.

https://gateoverflow.in/1251/gate2007_53

0
There is a difference between Left linear grammar and left recursion. regular languages are either Left linear or Right linear. LL(1) does not accept left recursion. Left linear grammar is a kind of left recursion . every left linear grammar can be converted into equivalent right linear grammar.

LL Grammar
Grammars which can be parsed by an LL parser.

LL parser
Parses the input from Left to right, and constructs a Leftmost derivation of the sentence(i.e. it is always the leftmost non-terminal which is rewritten). LL parser is a top-down parser for a subset of context-free languages.
An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence and can do it without backtracking.

Consider a Grammar $G$:
$S \rightarrow a|aa$

this grammar is Regular but cannot be parsed by a LL(1) parser w/o backtracking, coz here, lookahead is of 1 symbol only and in the grammar for both productions, parser while looking at just one(first) symbol, which is $a$, fails to select the correct rule for parsing.

Hence, not every Regular grammar is LL(1); Statement P is False.

LR Grammar
Grammars which can be parsed by
LR parsers.

LR Parsers
thery are a type of bottom-up parsers that efficiently handle deterministic context-free languages(DCFL) in guaranteed linear time.

all Regular Languages are also DCFL hence, They all can be parsed by a LR(1) grammar.

Hence, Statement Q is True.

selected
0
Can we say that there  exist a LL(1) grammar for every regular language ..?
+1
Yes
+3
Statement P is for regular Grammar(Regular Grammar may be ambiguous) , not for regular Language..

As DFA is deterministic for every input Alphabet and move is fixed to a particular state.. So, I think we may convert it to LL(1) Grammar..
+9
LR(0) cannot parse all regular languages. We cannot have a LR(0) for a*.
0
Can't the equivalent grammer of  S->a|aa be equal to

S->aS'

S'->S|epsilon

which is LL(1).
0
@arjun sir

u meant a* or a+?
+1
both works- both cannot have LR(0).
0
@Arjun sir

for a* the grammar is

S->aS|∊ and this can be parsed by a LR(0) parser. so how a* cant be done?
0
How is it LR(0)?
0
There is no shift reduce or reduce reduce conflict..thats why.. Am i right?
+9
If we have one look-ahead then there is no conflict. With 0 look-ahead there is conflict. Initially itself there is a conflict as to reduce using empty string or shift. Actually LR(0) generates the same language as accepted by a DPDA which accepts by empty stack. So, it must have the prefix property- if a string "w" is in L, no prefix of "w" can be in L.
0
Thanks I got it  :)
0

S→a|aa

regular grammars are of type V ==> VT*/T(left recursive) or V ==> T*V/T(right recursive)

Is this valid example I mean it should be like

S ==> a| aB

B==> a

0

In the Context of what @Arjun Sir Said,

Take grammar for $L(G)=a^*$ as $S->aS| \epsilon$

The first state itself I0, will have SR conflict, so not LR(0).

Similarly for $L(G)=a^+$, take grammar $S->aS|a$

From the intial state, after shifting a we get into state say I1 which has below LR(0) items

$S->a.S\\S>.aS\\S->a.$ here SR conflict occured and hence not LR(0).

So, LR(0), cannot parse all regular languages.

P: This is false.

Every regular language is LL(1) meaning we have a LL(1) grammar for it. But we can not say same about every Regular Grammar. For example, every regular language can be represented by Left & Right Linear Grammar, where Left Linear Grammar is not LL(1), Right linear is.

Example $aa$* we can represent this as $S \rightarrow Sa|a$ which is not LL(1) ,but $S \rightarrow a|aS$ is LL(1).

Q: This is true because of every LL(1) is LR(1).

All regular sets have Right recursive grammar, which is LL(1) & Every LL(1) is LR(1).

We can also say that LR(1) accepts DCFL & Regular languages are subset of DCFL.

edited by
0
0
every right recursive grammar is not ll(1)

E-->T+E/T

T--->F*T/F

F-->id

is this ?
0

Every LL(1) grammar is LR(1) grammar.

But, every LR(1) grammar need not be LL(1) grammar

Is this true ?

0
Yes, every LR(1) grammar need not be LL(1).
0
What is regular set and regular language?

Getting confused here.

Can we say that regular language is a regular set?
0

Regular set/language refers to the set of strings generated by a regular grammar/regular expression or a Finite Automata. Multiple regular grammar can generate the same regular set.

From the first line it seems that both the term have identical meaning.

0
If both are same, we can have an ambiguous regular grammar for the regular language, in that case, even statement Q will be false.

Correct me if i am wrong.
0
Multiple regular grammar can have the same regular set. So for a regular set, you may show me a ambiguous grammar and say that it is not LR(1), I will counter it by showing you another grammar for the same regular set and say that it is LR(1).

So, I am also confused now.
0
Same here, in confusion state.
0
LR(1) is the property of grammar, not of language.
P : FALSE because a left-linear regular grammar can be left-recursive and left recursive languages cannot be LL(1)

Q: TRUE because every regular set (or language) has a right-linear deterministic (or left-factored) unambiguous grammar and thus, every regular language can have an LL(1) grammar. Since every LL(1) grammar is also LR(1), Q is true.

NOTE : For, every regular language, there exists an unambiguous grammar because regular languages are acceptable by DFAs and unambiguity is a property of non-determinism.
edited
+2

@Vishal Goel

NOTE : Every regular language is inherently unambiguous

this statement is not correct,

if a language L is inherently unambigous it means, that every grammer generating L will be unambigous....this is not true..

for eg:

let regular language, L = {a}

now one grammer for L could be, S->aA/a   A->$\epsilon$..........and this grammer is ambigous.

+1
By the term "inherently unambiguous language", I had meant that there exists at least one unambiguous grammar for the language. But, I think, the term doesn't really exist. So, I have edited my answer. Thanks for pointing it out.
since every regular set can be written is left recursive as well in right recursive and a grammar written in right recursive is LL(1) and we know every LL(1) is LR(1) . So it is true
P- Every regular grammar may or may not be LL(1). We cannot assure that. The statement given is assuring that and is hence false.

Q- This says that there is atleast one grammar in the regular set which is LR(1). Which is true.

Therefore option C is correct.
0
@arjun sir finally need ur help plz gives the reason why B is correct . i m fade up by above comments all are seems to be confusing to me. i did not get clear explanation for option B till this date plz tell me sir

option A is FALSE because regular grammar can be ambiguous and LL(1) do not parse ambiguous grammar.
S-> aA / B
A-> d
moreover this is also non-determinstic grammar because First of S= {a,a} and LL(1) grammar can parse non-deterministic grammar also.

There is a difference between Left linear grammar and left recursion. regular languages are either Left linear or Right linear. LL(1) does not accept left recursion. Left linear grammar is a kind of left recursion. But every left linear grammar can be converted into equivalent right linear grammar.

LR(1) grammar parse D-CFL language and every regular language is also CFL so option B is TRUE

edited

1
2