8.9k 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

| 8.9k views
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

+2
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 recursion is a kind of left-linear grammar. 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\mid aa$

This grammar is Regular but cannot be parsed by a LL(1) parser w/o backtracking, because 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 Parser: They 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.

by Boss (30.7k points)
selected
0
Can we say that there  exist a LL(1) grammar for every regular language ..?
+2
Yes
+5
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..
+15
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+?
+2
both works- both cannot have LR(0).
+1
@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)?
+1
There is no shift reduce or reduce reduce conflict..thats why.. Am i right?
+12
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

+3

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.

0

@Arjun Sir,

LR(0) generates the same language as accepted by a DPDA which accepts by empty stack.

Sir would it be valid to say that acceptance by final state is more powerful concurring from this statement? Because, LR(1) grammar would also be accepted by DPDA with final state where as it wouldn't be by DPDA with empty stack?

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.

by (159 points)
edited by
+7

Yes, every LL(1) grammar is guaranteed to be LR(1).
​

http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/12-Miscellaneous-Parsing.pdf

0
@Akash Every right linear grammar is LL(1)?

Also, every right recursive grammar is LL(1)?
0
@anurag  or any one plz tell me s->a/ab is having left factoring or not .  according to me yes
0
S->a|aS, So How it is LL(1)?
+1
@rajan you are right.

But i have another doubt : Is every right linear grammar LL(1)?

S->aS|a is not because there is non-determinism.
0
nopes bcz take this  S->aS/a/epsilon  it is right linear bt ambiguous too so LL(1) never parse it  and even every left linear grammer is LL(1) also false
0

What do question mean by "Every regular set"? How it differs from statement P?

Explain This very clearly.

Thanks.
+3
Regulat 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.
0
what if it says all regular set is LL(1) grammar?
0

"but S->a|aS is LL(1)."  How it is LL(1) ? We will get two entries in M[S,a]

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.
by Active (1.8k points)
edited
+3

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

+2
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
by Active (4.8k points)
by Loyal (8.6k points)
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.
by Boss (19.9k points)
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/a   A->ϵ

Some ambiguous grammars can be converted into unambiguous grammars, but no general procedure for doing this as no algorithm exists for detecting ambiguous grammars.

Although left linear grammar is not accepted by LL(1) but we can convert every LLG to equivalent RLG.
Moreover, this is also non-deterministic grammar because First of S= {a,a} and LL(1) grammar can parse non-deterministic grammar also but we can convert every non-deterministic grammar to deterministic grammar as well.

There is a difference between Left linear grammar and left recursion. regular languages are either Left linear or Right linear. . Left recursion is a kind of left-linear grammar.

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

by Active (3.5k points)
edited
• P: Every regular grammar is LL(1)

False, because Regular Grammars can be Left Recursive.

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

LR(1) grammars = Grammars of Bottom-Up Parsers = Grammars that generate DCFLs.

DCFLs are subsets of RLs. For example, {$a^{n} b^{n} | n>1$} is a subset of $(a+b)^*$

Hence, every regular can generate a DCFL. True.

Option C is correct.

by Active (2.2k points)

1
2
3