📘 1. Introduction
In compiler construction, Regular Expressions (RE) and Finite Automata (FA) are used in the lexical analyzer to define and recognize tokens.
👉 Relationship (Very Important):
Regular Expression → Finite Automaton → Token Recognition
🧠 2. Regular Expressions (RE)
✅ Definition
A Regular Expression is a pattern used to describe a set of strings.
👉 It defines how tokens (like identifiers, numbers) are formed.
🔤 Basic Symbols in Regular Expressions
| Symbol |
Meaning |
|
a |
single character |
|
| `a |
b` |
OR |
ab |
concatenation |
|
a* |
zero or more a |
|
a+ |
one or more a |
|
( ) |
grouping |
|
📌 Examples
1. Identifier
letter (letter | digit)*
👉 Matches:
x, var1, total99
2. Integer Number
digit+
👉 Matches:
10, 245, 999
3. Keywords
if | else | while
🎯 Key Properties
- Defines patterns, not actual strings
- Used in token specification
- Easy to convert into automata
⭐ Important (Exam)
👉 RE describes WHAT to match
🔍 3. Finite Automata (FA)
✅ Definition
A Finite Automaton is a machine used to recognize strings that follow a pattern.
👉 It checks whether input belongs to a language or not.
📦 Components of FA
- States (Q)
- Alphabet (Σ)
- Transition function (δ)
- Start state (q0)
- Final/Accepting states (F)
📊 General Diagram
→ (q0) --a--> (q1) --b--> (q2*)
- q0 = start
- q2 = accepting state
🔄 4. Types of Finite Automata
🔹 1. NFA (Non-Deterministic Finite Automaton)
✅ Definition
An automaton where:
- One state can have multiple transitions for same input
- Can move without input (ε-moves)
📊 Example NFA
(q0) --a--> (q1)
(q0) --a--> (q2)
⭐ Features
- Multiple paths possible
- Easier to design
- Not efficient for implementation
🔹 2. DFA (Deterministic Finite Automaton)
✅ Definition
An automaton where:
- Each state has exactly one transition per input
- No ε-moves
📊 Example DFA
(q0) --a--> (q1)
(q1) --b--> (q2*)
⭐ Features
- Only one path
- Fast and efficient
- Used in compilers
⚖️ 5. Difference Between DFA and NFA
| Feature |
DFA |
NFA |
| Transitions |
One per input |
Multiple possible |
| ε-moves |
Not allowed |
Allowed |
| Speed |
Fast |
Slower |
| Implementation |
Easy |
Complex |
| Use |
Practical systems |
Theory/design |
🔗 6. Relationship Between RE and FA
🔄 Conversion Steps (Very Important)
- Regular Expression → NFA
- NFA → DFA
- DFA → Token Recognizer
📊 Flow Diagram
Regular Expression → NFA → DFA → Token Recognition
⭐ Key Point (Exam)
👉 “Every Regular Expression can be converted into DFA”
🧪 7. Example (RE to FA)
Given RE:
a*
Strings accepted:
ε, a, aa, aaa, ...
DFA Representation
(q0*) --a--> (q0*)
- q0 is start and accepting state
🧪 8. Example (Identifier Recognition)
RE:
letter (letter | digit)*
DFA:
(q0) --letter--> (q1*)
(q1) --letter/digit--> (q1*)
⚠️ 9. Applications in Compiler
- Token recognition
- Pattern matching
- Lexical analyzer design
🎯 10. Important Exam Concepts
👉 Frequently asked:
- Define Regular Expression
- Define Finite Automata
- Difference between DFA and NFA
- RE for identifier/number
- Convert RE → DFA
- Draw DFA diagrams
- Explain relationship between RE and FA
📝 11. Short Notes (Quick Revision)
Regular Expression
- Pattern description
- Used in token specification
Finite Automata
- Pattern recognition machine
- Used in lexical analysis
Key Relation
RE → NFA → DFA → Token Recognition
📊 12. Final Summary Table
| Aspect |
Regular Expression |
Finite Automata |
| Definition |
Pattern description |
Pattern recognition machine |
| Purpose |
Specify tokens |
Recognize tokens |
| Nature |
Declarative |
Operational |
| Types |
— |
DFA, NFA |
| Usage |
Before scanning |
During scanning |
| Example |
digit+ |
DFA for numbers |
| Conversion |
→ NFA/DFA |
From RE |
✅ Final Conclusion
- Regular Expressions define the structure of tokens
- Finite Automata recognize those tokens
- Together, they form the core of lexical analysis