ed/LangStudies
1
0
Fork 0
mirror of https://github.com/Ed94/LangStudies.git synced 2024-09-20 05:07:33 -07:00
Code Issues Packages Projects Releases Wiki Activity
main
LangStudies/App/RegM/Lectures/Lecture.1.Notes.md

813 B
Raw Permalink Blame History

Automata Theory: Building a RegExp machine

Content:

State Machines Formal Grammars Implement a regular expression processor

History:

Pioneers:

1951 - Stephen Kleene invented reg exp (sets).

Reuglar Langauge : Langauge recognized by a finite automata (state machines). Kleene's Therem : Equivalence of regular expressions and finite automata.

Has a notation named after him: Kleene-Closure (AKA: Kleene star) : A* (Stands for repetition)

1956 - Chomsky defines his hiearchy fo grammers

Regular grammers are considered a type 3. See: https://en.wikipedia.org/wiki/Chomsky_hierarchy

img

Thus they are the weakest form of grammars.

1968 - Ken Thompson used them for pattern matching in strings, and lexical analysis (scanners)

NFA - Thompson construction