2 deleted 2 characters in body
source | link
`AA -> ωα_1ωα1 | ωα_2ωα2 | ... | ωα_n` (where `_i` is an index, not the terminal `_` and `i`)ωαn

(where αi is the i-th α, not the symbols α and i), with α_1α1α_2α2 ≠ ... ≠ α_nαn. We can then easily show that:

`∩(i=1,..,n) FIRST(α_iωαi) ≠ Ø`Ø
`SS -> Sα | β`β
`A -> ωα_1 | ωα_2 | ... | ωα_n` (where `_i` is an index, not the terminal `_` and `i`)

with α_1α_2 ≠ ... ≠ α_n. We can then easily show that:

`∩(i=1,..,n) FIRST(α_i) ≠ Ø`
`S -> Sα | β`
A -> ωα1 | ωα2 | ... | ωαn

(where αi is the i-th α, not the symbols α and i), with α1α2 ≠ ... ≠ αn. We can then easily show that:

(i=1,..,n) FIRST(ωαi) ≠ Ø
S -> Sα | β
1
source | link

I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:

We start by writing the three rules of the definition of an LL(1) grammar:

For every production A -> α | β with α ≠ β:

  1. FIRST(α) ∩ FIRST(β) = Ø.
  2. If β =>* ε then FIRST(α) ∩ FOLLOW(A) = Ø (also, if α =>* ε then FIRST(β) ∩ FOLLOW(A) = Ø).
  3. Including ε in rule (1) implies that at most one of α and β can derive ε.

Proposition 1: A non-factored grammar is not LL(1).

Proof:

If a grammar G is non-factored then there exists a production in G of the form:

`A -> ωα_1 | ωα_2 | ... | ωα_n` (where `_i` is an index, not the terminal `_` and `i`)

with α_1 ≠ α_2 ≠ ... ≠ α_n. We can then easily show that:

`∩(i=1,..,n) FIRST(α_i) ≠ Ø`

which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎

Proposition 2: A left-recursive grammar is not LL(1).

Proof:

If a grammar is left-recursive then there exists a production in G of the form:

`S -> Sα | β`

Three cases arise here:

  1. If FIRST(β) ≠ {ε} then:

        FIRST(β) ⊆ FIRST(S)

    =>  FIRST(β) ∩ FIRST(Sα) ≠ Ø

    which contradicts rule (1) of the definition.

  2. If FIRST(β) = {ε} then:

    2.1. If ε ∈ FIRST(α) then:

    ε ∈ FIRST(Sα)

    which contradicts rule (3) of the definition.

    2.2. If ε ∉ FIRST(α) then:

        FIRST(α) ⊆ FIRST(S) (because β =>* ε)

    =>  FIRST(α) ⊆ FIRST(Sα) ........ (I)

    we also know that:

    FIRST(α) ⊆ FOLLOW(S) ........ (II)

    by (I) and (II), we have:

    FIRST(Sα) ∩ FOLLOW(S) ≠ Ø

    and since β =>* ε, this contradicts rule (2) of the definition.

In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎

Proposition 3: An ambiguous grammar is not LL(1).

Proof:

While the above proofs are mine, this one is not, it's by Kevin A. Naudé which I got from his answer that is linked below:

https://stackoverflow.com/a/18969767/6275103