The Gateway to Computer Science Excellence

+1 vote

1. Above grammer is **not left factored** , actually *hidden left factors *are there in this grammer

[Ref : PAGE 9

https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/080%20Formal%20Grammars.pdf]

2. Since it is not left factored hence it is** not deterministic.**

3.** Yes , **every left factored grammer is deterministic.

0 votes

i think the grammar is left factored

and yes, the purpose of making the grammar left factored is making it deterministic.

correct me, if i am wrong

and yes, the purpose of making the grammar left factored is making it deterministic.

correct me, if i am wrong

0

What is defination of deterministic grammer ?? I think grammer where there is no backtracking possible is deterministic. Is it true...

+1

Consider an example:

A->aB | aBC

here, we on seeing 'a' we are not sure to go for aB or aBC. Such kinds of Grammers are Non deterministic.

Now, about deterministic grammer,

given question is it's example. We exactly know where to go on seeing input.

And yes, No Backtracking = Deterministic

A->aB | aBC

here, we on seeing 'a' we are not sure to go for aB or aBC. Such kinds of Grammers are Non deterministic.

Now, about deterministic grammer,

given question is it's example. We exactly know where to go on seeing input.

And yes, No Backtracking = Deterministic

0

I understand your point , but my doubt is , say e.g. if we want to derive ac , then if we go through S->Aa then we will never get ac so we will need to backtrack , is it not backtracking ??

0

Here in my question the first symbol is non terminal (**A**a or **B**c) , so how can you choose production (whether to use Aa or Bc) ?? This is what i am not understanding. There is no such hint about whether to choose "Bc to derive ac". So how can it is deterministic ??

0

Oh! I'm also confused there! But from above link

if we want 'ac' as op, then it'll go for Bc. Again why? see above marked comment. But I'm also not sure about it because it'll require a look ahead to see next input and then go for Bc.

0

Actually lookaheads shouldn't be the factor , because if i will take example S->AAa | BBc ; A -> a ; B -> a ; then to derive aac we will require two lookaheads to make decision. Also in picture that you have quoted, it is easily decidable by seeing only first symbol itself (whether we need b,c,d) so there is no issue here.....

0 votes

1. Left factoring is use to remove non determinism....means for a given input string if we cant decide on seeing a symbol which production to use...

Here, We don't need to take any decision on seeing input, Hence, Left factored.

2&3. As

Left factoring is use to remove non determinism

every left factored grammer is deterministic.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,490 answers

195,432 comments

100,654 users