Documentation

Linglib.Core.Computability.ContextFreeGrammar.Regular

Context-free and regular languages #

Over a finite alphabet, every regular language is context-free: the right-linear grammar M.toContextFreeGrammar of a finite automaton M generates the language of M. The intersection of a context-free language with a regular language is context-free. The grammar G.inter M is the triple construction: its nonterminals are the nonterminals of G annotated with an entry and an exit state of M, and a rule of G yields one rule for every way of threading the states of M through its right-hand side. A fresh start symbol rewrites to the start nonterminal of G between the start state and each accepting state of M.

Main definitions #

Main results #

Implementation notes #

The right-linear grammar of M has a nonterminal for each state, a rule q → a q' for each transition from q to q' on the letter a, and a rule q → ε for each accepting state q; its sentential forms are a word w followed by the state M.eval w, or an accepted word. The alphabet must be finite, because a grammar has finitely many rules and so uses finitely many letters: over an infinite alphabet the language of all words is regular, by a one-state automaton, but not context-free.

References #

def DFA.toContextFreeGrammar {α : Type u_1} {σ : Type} [Fintype α] [Fintype σ] (M : DFA α σ) [DecidablePred fun (x : σ) => x ∈ M.accept] :
ContextFreeGrammar α

The right-linear grammar of M has a nonterminal for each state, a rule q → a (M.step q a) for each state q and letter a, and a rule q → ε for each accepting state q.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem DFA.mem_rules_toContextFreeGrammar {α : Type u_1} {σ : Type} [Fintype α] [Fintype σ] {M : DFA α σ} [DecidablePred fun (x : σ) => x ∈ M.accept] {r : ContextFreeRule α σ} :
    r ∈ M.toContextFreeGrammar.rules ↔ (∃ (a : α), r.output = [Symbol.terminal a, Symbol.nonterminal (M.step r.input a)]) ∨ r.input ∈ M.accept ∧ r.output = []
    theorem DFA.derives_toContextFreeGrammar {α : Type u_1} {σ : Type} [Fintype α] [Fintype σ] {M : DFA α σ} [DecidablePred fun (x : σ) => x ∈ M.accept] (w : List α) :
    M.toContextFreeGrammar.Derives [Symbol.nonterminal M.start] (List.map Symbol.terminal w ++ [Symbol.nonterminal (M.eval w)])
    theorem DFA.derives_toContextFreeGrammar_iff {α : Type u_1} {σ : Type} [Fintype α] [Fintype σ] {M : DFA α σ} [DecidablePred fun (x : σ) => x ∈ M.accept] {v : List (Symbol α σ)} :
    M.toContextFreeGrammar.Derives [Symbol.nonterminal M.start] v ↔ ∃ (w : List α), v = List.map Symbol.terminal w ++ [Symbol.nonterminal (M.eval w)] ∨ v = List.map Symbol.terminal w ∧ M.eval w ∈ M.accept
    theorem DFA.language_toContextFreeGrammar {α : Type u_1} {σ : Type} [Fintype α] [Fintype σ] {M : DFA α σ} [DecidablePred fun (x : σ) => x ∈ M.accept] :
    M.toContextFreeGrammar.language = M.accepts

    The grammar of M generates the language of M.

    inductive ContextFreeGrammar.Annotates {T : Type u_1} {N : Type u_2} {σ : Type} (M : DFA T σ) :
    σ → List (Symbol T (Option (σ × N × σ))) → List (Symbol T N) → σ → Prop

    Annotates M p l out q says that the sentential form l is out with every nonterminal A replaced by some some (p', A, q') so that the states thread from p to q. A terminal advances the automaton, and an annotated nonterminal jumps from its entry state to its exit state.

    • nil {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} (p : σ) : Annotates M p [] [] p
    • terminal {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} (a : T) {l : List (Symbol T (Option (σ × N × σ)))} {out : List (Symbol T N)} (h : Annotates M (M.step p a) l out q) : Annotates M p (Symbol.terminal a :: l) (Symbol.terminal a :: out) q
    • nonterminal {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p p' q : σ} (A : N) {l : List (Symbol T (Option (σ × N × σ)))} {out : List (Symbol T N)} (h : Annotates M p' l out q) : Annotates M p (Symbol.nonterminal (some (p, A, p')) :: l) (Symbol.nonterminal A :: out) q
    Instances For
      theorem ContextFreeGrammar.Annotates.append {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q r : σ} {l₁ l₂ : List (Symbol T (Option (σ × N × σ)))} {out₁ out₂ : List (Symbol T N)} (h₁ : Annotates M p l₁ out₁ q) (h₂ : Annotates M q l₂ out₂ r) :
      Annotates M p (l₁ ++ l₂) (out₁ ++ out₂) r
      theorem ContextFreeGrammar.Annotates.split_out {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p r : σ} {l : List (Symbol T (Option (σ × N × σ)))} {out₁ out₂ : List (Symbol T N)} (h : Annotates M p l (out₁ ++ out₂) r) :
      ∃ (l₁ : List (Symbol T (Option (σ × N × σ)))) (l₂ : List (Symbol T (Option (σ × N × σ)))) (q : σ), l = l₁ ++ l₂ ∧ Annotates M p l₁ out₁ q ∧ Annotates M q l₂ out₂ r
      theorem ContextFreeGrammar.Annotates.split {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p r : σ} {l₁ l₂ : List (Symbol T (Option (σ × N × σ)))} {out : List (Symbol T N)} (h : Annotates M p (l₁ ++ l₂) out r) :
      ∃ (out₁ : List (Symbol T N)) (out₂ : List (Symbol T N)) (q : σ), out = out₁ ++ out₂ ∧ Annotates M p l₁ out₁ q ∧ Annotates M q l₂ out₂ r

      An annotation that is a concatenation annotates a concatenation.

      theorem ContextFreeGrammar.Annotates.map_terminal {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} (p : σ) (w : List T) :
      Annotates M p (List.map Symbol.terminal w) (List.map Symbol.terminal w) (M.evalFrom p w)
      theorem ContextFreeGrammar.Annotates.eq_of_map_terminal_right {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} {l : List (Symbol T (Option (σ × N × σ)))} {w : List T} (h : Annotates M p l (List.map Symbol.terminal w) q) :
      l = List.map Symbol.terminal w ∧ q = M.evalFrom p w
      theorem ContextFreeGrammar.Annotates.eq_of_map_terminal_left {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} {out : List (Symbol T N)} {w : List T} (h : Annotates M p (List.map Symbol.terminal w) out q) :
      out = List.map Symbol.terminal w ∧ q = M.evalFrom p w
      theorem ContextFreeGrammar.Annotates.eq_of_singleton_right {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} {l : List (Symbol T (Option (σ × N × σ)))} {A : N} (h : Annotates M p l [Symbol.nonterminal A] q) :
      l = [Symbol.nonterminal (some (p, A, q))]
      theorem ContextFreeGrammar.Annotates.eq_of_singleton_left {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} {out : List (Symbol T N)} {p₀ q₀ : σ} {A : N} (h : Annotates M p [Symbol.nonterminal (some (p₀, A, q₀))] out q) :
      out = [Symbol.nonterminal A] ∧ p₀ = p ∧ q₀ = q
      theorem ContextFreeGrammar.Annotates.none_notMem {T : Type u_1} {N : Type u_2} {σ : Type} {M : DFA T σ} {p q : σ} {l : List (Symbol T (Option (σ × N × σ)))} {out : List (Symbol T N)} (h : Annotates M p l out q) :
      Symbol.nonterminal none ∉ l
      noncomputable def ContextFreeGrammar.annotations {T : Type u_1} {N : Type u_2} {σ : Type} (M : DFA T σ) [Fintype σ] :
      σ → List (Symbol T N) → Finset (σ × List (Symbol T (Option (σ × N × σ))))

      The annotations of out from state p, each with its exit state.

      Equations
      Instances For
        theorem ContextFreeGrammar.mem_annotations {T : Type u_1} {N : Type u_2} {σ : Type} (M : DFA T σ) [Fintype σ] {p : σ} {out : List (Symbol T N)} {x : σ × List (Symbol T (Option (σ × N × σ)))} :
        x ∈ annotations M p out ↔ Annotates M p x.2 out x.1
        noncomputable def ContextFreeGrammar.inter {T : Type u_1} {σ : Type} [Fintype σ] (G : ContextFreeGrammar T) (M : DFA T σ) :
        ContextFreeGrammar T

        The grammar G.inter M generates the intersection of G with a finite automaton M. Its nonterminals are those of G annotated with entry and exit states, it has each rule of G in every annotation of its right-hand side, and its fresh start symbol none rewrites to the start nonterminal of G between the start state and each accepting state.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          @[simp]
          theorem ContextFreeGrammar.inter_initial {T : Type u_1} {σ : Type} (M : DFA T σ) [Fintype σ] {G : ContextFreeGrammar T} :
          (G.inter M).initial = none
          theorem ContextFreeGrammar.mem_inter_rules {T : Type u_1} {σ : Type} {M : DFA T σ} [Fintype σ] {G : ContextFreeGrammar T} {r' : ContextFreeRule T (G.inter M).NT} :
          r' ∈ (G.inter M).rules ↔ (r'.input = none ∧ ∃ q ∈ M.accept, r'.output = [Symbol.nonterminal (some (M.start, G.initial, q))]) ∨ ∃ r ∈ G.rules, ∃ (p : σ) (q : σ), r'.input = some (p, r.input, q) ∧ Annotates M p r'.output r.output q

          The grammar generates the intersection #

          theorem ContextFreeGrammar.Produces.of_inter {T : Type u_1} {σ : Type} {M : DFA T σ} [Fintype σ] {G : ContextFreeGrammar T} {l' t' : List (Symbol T (G.inter M).NT)} (step : (G.inter M).Produces l' t') {p q : σ} {out : List (Symbol T G.NT)} (h : Annotates M p l' out q) :
          ∃ (out' : List (Symbol T G.NT)), G.Produces out out' ∧ Annotates M p t' out' q
          theorem ContextFreeGrammar.Derives.of_inter {T : Type u_1} {σ : Type} {M : DFA T σ} [Fintype σ] {G : ContextFreeGrammar T} {l' t' : List (Symbol T (G.inter M).NT)} (hd : (G.inter M).Derives l' t') {p q : σ} {out : List (Symbol T G.NT)} (h : Annotates M p l' out q) :
          ∃ (out' : List (Symbol T G.NT)), G.Derives out out' ∧ Annotates M p t' out' q
          theorem ContextFreeGrammar.language_inter_le {T : Type u_1} {σ : Type} {M : DFA T σ} [Fintype σ] {G : ContextFreeGrammar T} :
          (G.inter M).language ≤ G.language ⊓ M.accepts
          theorem ContextFreeGrammar.exists_annotates_of_derives {T : Type u_1} {σ : Type} {M : DFA T σ} [Fintype σ] {G : ContextFreeGrammar T} {out : List (Symbol T G.NT)} {w : List T} (hd : G.Derives out (List.map Symbol.terminal w)) (p : σ) :
          ∃ (l : List (Symbol T (Option (σ × G.NT × σ)))), Annotates M p l out (M.evalFrom p w) ∧ (G.inter M).Derives l (List.map Symbol.terminal w)
          theorem ContextFreeGrammar.le_language_inter {T : Type u_1} {σ : Type} {M : DFA T σ} [Fintype σ] {G : ContextFreeGrammar T} :
          G.language ⊓ M.accepts ≤ (G.inter M).language
          theorem ContextFreeGrammar.language_inter {T : Type u_1} {σ : Type} [Fintype σ] (G : ContextFreeGrammar T) (M : DFA T σ) :
          (G.inter M).language = G.language ⊓ M.accepts

          Bar-Hillel's theorem: G.inter M generates the intersection.

          theorem Language.IsRegular.isContextFree {α : Type u_1} [Finite α] {L : Language α} (h : L.IsRegular) :
          L.IsContextFree

          Over a finite alphabet, every regular language is context-free.

          theorem Language.IsContextFree.inf_isRegular {α : Type u_1} {L R : Language α} (hL : L.IsContextFree) (hR : R.IsRegular) :
          (L ⊓ R).IsContextFree

          Context-free languages are closed under intersection with regular languages.