Skip to content

Latest commit

 

History

History
52 lines (27 loc) · 1.84 KB

README.md

File metadata and controls

52 lines (27 loc) · 1.84 KB

Grammars formally in Lean

Instructions

In order to install Lean 3, follow the manual.

In order to download this project, run leanproject get madvorak/grammars in your Unix-like command line.

In order to check that the proofs are correct, run ./mk from the root directory of this project.
The script will output Result: SUCCESS if everything builds successfully.

Overview

Below you find what has been completed so far.

Context-free grammars

Definition

Example

Closure under union

Closure under reversal

Closure under concatenation

Non-closure under intersection (*)

Non-closure under complement (*)

* missing proof: Context-free pumping lemma

Context-sensitive grammars

Example

Unrestricted grammars

(a.k.a. general grammars, a.k.a. type-0 grammars, a.k.a. recursively-enumerable grammars, a.k.a. phrase-structure grammars, a.k.a. grammars)

Definition

Example

Closure under union

Closure under reversal

Closure under concatenation

Closure under Kleene star