|Name||Math notation||Plain text||Other names||Other notations|
|Empty language||set: , Br:|
|Trivial language||set: , RE: , Br:|
|Rule||Language equation||BNF: |
|Concatenation||sequence, cartesian p.||, Might: , set:|
|Unordered choice||X|Y||union, disjunction||RE: , set:|
|Kleene star||Kleene closure||Might:|
|Kleene plus||, |
|Negation||absolute complement||set: , ,|
|Set of characters||set:|
|Negation of set|
|End of file|
There are a lot of different formalisms about languges and they all use slightly different notations, but in the end it’s the same thing.
Regular expressions doesn’t use symbols and rules to define language. There is only one rule - regular expression. Classical regular expressions use only tokens, concatenation, unordered choice and Kleene star. Also in science papers they don’t bother to put quotes around letters - this way notation is more terse.
Regular Expressions Extended
Same as classical regular expressions, but also adds intersection and negation (which makes it full set of Boolean operations). Those two operations doesn’t add to calculation power (still can produce only regular languages).
See: Janusz A. Brzozowski. 1964. Derivatives of Regular Expressions. J. ACM 11, 4 (Oct. 1964), 481–494. https://doi.org/10.1145/321239.321249
Modern regular expressions
Modern regular expressions add some more tricks, like: Kleene plus, Optional, Quantifier, Any character, Range, Set of characters, Negation of set, Escape sequences. Depends on the flavor (implementation). Those, again, doesn’t add to computational power, but they are quite convenient.
Chomsky generative grammar
Chomsky grammar uses: symbols (non-terminals), rules, tokens (terminals), concatenation, unordered choice.
Becuase ”” is unordered choice those are the same rules:
Depending on which restrictions you put on the rules it can genrate: regular, context-free, context-sensitive, recursive enumerable languages. This formalism is used to define Chomsky hierarchy.
BNF is variation of Chomsky grammar which can generate only context-free languages. There are a lot of variations which also add: Kleene plus, Optional, Quantifier, Any character, Range, Set of characters, Negation of set, Escape sequences. Which doesn’t add anything to computational power, but makes it more practical. BNF looks like this
<S> ::= "" | "a"
Parsing Expression Grammars
PEG again can be treated as variation of Chomsky grammar, but instead of unoredered choice it uses ordered chocie and also adds positive lookahead, negative lookahead and any character. PEG can recognize some context-sensitive grammars. PEG looks like this:
Parsing with Derivatives
PwD adds to classical regular expressions: rules and symbols (which allows to do general recursion). PwD can handle context-free languages. You can express Kleene closure in three ways:
You can as well say that they added Kleene star to Chomsky grammar.
It adds intersection to Chomsky grammar. It can handle some context-sensitive languages. It looks like this (in original paper they use instead of ):
It adds intersection and negationto Chomsky grammar. It can handle some context-sensitive languages.
Interesting: in PwD they added general recursion to classical regular expressions to recieve context-free Chomsky grammar. If we add general recursion to REE we will recieve Boolean grammar.
Regular Expressions with Lookahead
REwLA adds positive and negative lookaheads to classical regular expressions.
Interesting: in PwD they added general recursion to classical regular expressions to recieve context-free Chomsky grammar. If we add general recursion to REwLA we will recieve PEG. And ordered choice can be expressed as .
There is an interesting story behind how notation changed over time. See this video
- 1951 Stephen Kleene develops regular expressions to describe McCulloch-Pitts (1943) nerve nets (uses
∨for choice; considers postfix
∗, but decides to make it a binary operator to avoid having empty strings:
x∗ymeans any number of copies of
x, followed by
- 1956 Journal publication of Kleene’s technical report: binary
- 1958 Copi, Elgot, and Wright formulate REs using
- 1962 Janusz Brzozowki uses binary
∨and introduces postfix
- 1968 Ken Thompson’s paper “Regular Expression Search Algorithm” uses
- 1973 Thompson creates
ededitor for use by Doug McIlroy.
- 1975 Alfred Aho creates
- 1978 CMU Alphard project uses regular expressions with
- 1981 CMU FEG and IDL use regular expressions with
Operations concept map
TODO: I need to update it and explain abbreviations.