The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+36 votes
6.3k 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

asked in Compiler Design by Veteran (59.7k points) | 6.3k 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

6 Answers

+38 votes
Best answer

answer = option C

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.

answered by Boss (30.9k points)
selected by
0
Can we say that there  exist a LL(1) grammar for every regular language ..?
0
Yes
+2
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..
+6
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+?
0
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?
+5
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  :)
+40 votes

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.

So Answer is C.

answered by (159 points)
edited by
0
is Left linear grammar is left recursive grammar ? Please help me to understand.
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.
+5 votes
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.
answered by Active (1.6k points)
edited by
0

@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.
+3 votes
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
answered by Active (4.9k points)
0 votes
answer - C
answered by Loyal (8.8k points)
0 votes
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.
answered 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
Answer:

Related questions



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

44,285 questions
49,776 answers
164,297 comments
65,856 users