Automata Theory Tutorial
Classification of Grammars
Regular Grammar
Context-Free Grammars
Pushdown Automata
Turing Machine
Decidability
Automata Theory Useful Resources
Selected Reading
- Moore & Mealy Machines
- DFA Minimization
- NDFA to DFA Conversion
- Non-deterministic Finite Automaton
- Deterministic Finite Automaton
- Automata Theory Introduction
- Automata Theory - Home
Classification of Grammars
Regular Grammar
- DFA Complement
- Pumping Lemma for Regular Grammar
- Constructing FA from RE
- Regular Sets
- Regular Expressions
Context-Free Grammars
- Pumping Lemma for CFG
- Greibach Normal Form
- Chomsky Normal Form
- CFG Simplification
- CFL Closure Properties
- Ambiguity in Grammar
- Context-Free Grammar Introduction
Pushdown Automata
- PDA & Parsing
- PDA & Context Free Grammar
- Pushdown Automata Acceptance
- Pushdown Automata Introduction
Turing Machine
- Linear Bounded Automata
- Semi-Infinite Tape Turing Machine
- Non-Deterministic Turing Machine
- Multi-Track Turing Machine
- Multi-tape Turing Machine
- Accepted & Decided Language
- Turing Machine Introduction
Decidability
- Post Correspondence Problem
- Rice Theorem
- Turing Machine Halting Problem
- Undecidable Language
- Language Decidability
Automata Theory Useful Resources
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Regular Expressions
Regular Expressions
A Regular Expression can be recursively defined as follows −
ε is a Regular Expression indicates the language containing an empty string. (L (ε) = {ε})
φ is a Regular Expression denoting an empty language. (L (φ) = { })
x is a Regular Expression where L = {x}
If X is a Regular Expression denoting the language L(X) and Y is a Regular Expression denoting the language L(Y), then
X + Y is a Regular Expression corresponding to the language L(X) ∪ L(Y) where L(X+Y) = L(X) ∪ L(Y).
X . Y is a Regular Expression corresponding to the language L(X) . L(Y) where L(X.Y) = L(X) . L(Y)
R* is a Regular Expression corresponding to the language L(R*)where L(R*) = (L(R))*
If we apply any of the rules several times from 1 to 5, they are Regular Expressions.
Some RE Examples
| Regular Expressions | Regular Set |
|---|---|
| (0 + 10*) | L = { 0, 1, 10, 100, 1000, 10000, … } |
| (0*10*) | L = {1, 01, 10, 010, 0010, …} |
| (0 + ε)(1 + ε) | L = {ε, 0, 1, 01} |
| (a+b)* | Set of strings of a’s and b’s of any length including the null string. So L = { ε, a, b, aa , ab , bb , ba, aaa…….} |
| (a+b)*abb | Set of strings of a’s and b’s ending with the string abb. So L = {abb, aabb, babb, aaabb, ababb, …………..} |
| (11)* | Set consisting of even number of 1’s including empty string, So L= {ε, 11, 1111, 111111, ……….} |
| (aa)*(bb)*b | Set of strings consisting of even number of a’s followed by odd number of b’s , so L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, …………..} |
| (aa + ab + ba + bb)* | String of a’s and b’s of even length can be obtained by concatenating any combination of the strings aa, ab, ba and bb including null, so L = {aa, ab, ba, bb, aaab, aaba, …………..} |