definitions
- Σ Alphabet of Terminals
- I: Alphabet of Intermediates or Nonterminals
- ε = emtpy word
- Language = set of words ⊆ Σ*
- Rule A → x with A ∈ I and x ∈ (Σ ∪ I)*
- G Grammar = set of rule (with or of rules with same left hand side)
- φ → ψ meand ∃ α, β ∈ (Σ ∪ I)*, A → x ∈ G with
- φ = α A β
- ψ = α x β
- ⇒ transitive closure of →
- L(A) = {w ∈ Σ* | A ⇒ w}
- L≤i(A) = {w ∈ L(A) | len(w) ≤ i}
- Li+(A) = {w ∈ Σi | ∃ v ∈ Σ+ with wv ∈ L(A)} prefixes of len i
- B(A) = {w ∈ Σ* | ∃ v in L(A) \ ε with vw ∈ L(A)} Borders
- Bi(A) = {w ∈ Σ[0, i] | w ∈ B(A) or len(w) = i and ∃ v in Σ+ with wv in B(A)} Borders up to len i and prefixes