[Solved]: How to prove formally that grammar isn't LR(1)

Problem Detail: 

I want to prove that grammar $$ \begin{cases} S'\rightarrow S\\ S\rightarrow aSb ~|~ A\\ A\rightarrow bA~|~b \end{cases} $$ isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict.

I want to prove that without parser table, using another $LR(1)$ definition.

Here's definition: Grammar is $LR(1)$, if from

1. $S' \Rightarrow^*_r uAw \Rightarrow_r uvw$
2. $S' \Rightarrow^*_r zBx \Rightarrow_r uvy$
3. $FIRST(w) = FIRST(y)$

$\Rightarrow uAy=zBx.$

So how can prove that?

Asked By : Alvar

Answered By : wece

$$S'\Rightarrow^*\underbrace{ab}_uA\underbrace{b}_w\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{b}_w$$

$$S'\Rightarrow^*\underbrace{abbbb}_zA\underbrace{b}_x\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{bbbb}_y$$

$$FIRST(w)=FIRST(y)=b$$ But: $$abAbbbb=uAy\neq zBx=abbbbAb$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12470