Please enable JavaScript.
Coggle requires JavaScript to display documents.
Regular Language, Grammer, Kleene's theorem, Theorem 4.14, Sets,…
Regular Language
Transition graph
Transitions on strings
Thompsons contraction/Algo
Regular expression
operators
For or: + or |
NFA
Grammer
G=(V,Σ,S,P)
N non-terminals
starts with capital letters. A,B,C... or italic fonts
S starting symbols
P production rules
Σ Finite set of terminals
small letters. a,b,c... or bold font
String
word
phrase
sentence
Type 0
Context-sensitive
Type 1
Context-free
Type 2
Regular
Type 3
regular grammer
A -> α
A -> αB
A -> Bα
context free grammer
A ->σ
A -> λ
context sensitive grammer
aAB -> aσβ
recursively enumerable grammer
universal grammer
unrestricted grammer
α -> β
Language
Kleene's theorem
Kleene's closure
Theorem 4.14
For every Regular language there exists
FA
Eliminate condition
path leads to same destination
concatenate
Combining condition
same source/destination
use or
single symbol transitions
DFA
Subset constructin/Algo
Automata
minimal
Sets
Pushdown automata
PDA (pushdown automata)
REG
Thompson
NFA-Λ
remove λ
Brzozowski et McCluskey
Transition Graph