📘 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

1. States (Q)
2. Alphabet (Σ)
3. Transition function (δ)
4. Start state (q0)
5. 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)

1. Regular Expression → NFA
2. NFA → DFA
3. 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

---