Skip to content

madvorak/grammars

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

Formal grammars in Lean 3

Resources

License

Stars

Watchers

Forks

Languages