TOC-UNIT II

Unit-II

Regular Languages and Finite Automata

Regular Expressions, Regular Languages, Application of Finite Automata, Automata with output- Moore machine & Mealy machine, Finite Automata, Memory requirement in a recognizer, Definitions, union- intersection and complement of regular languages, Non Deterministic Finite Automata, Conversion from NFA to FA, ??- Non Deterministic Finite Automata, Conversion of NFA- ? to NFA, Kleene’s Theorem, Minimization of Finite automata, Regular And Non Regular Languages– pumping lemma.

2.1)REGULAR EXPRESSIONS

·       A Regular Expression (RE) is a symbolic notation used to describe patterns in strings over an alphabet. It is used to define Regular Languages.

·       A regular expression is basically a shorthand way of showing how a regular language is built from the base set of regular languages.

·       The symbols are identical which are used to construct the languages, and any given expression that has a language closely associated with it.

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.

Basic Symbols:

Symbol	Meaning	Example
a	A literal character	"a"
ε	Empty string	ε
∅	Empty language	∅
r1 + r2	Union (either r1 or r2)	a + b
r1r2	Concatenation	ab
r*	Kleene Star (zero or more reps)	a*

 

Examples:

a* → All strings with zero or more a (e.g., ε, a, aa, aaa)

(a + b)* → All strings of a and b in any order

a(a + b)* → Strings starting with a

✅ Example 1:

RE: a*
Meaning: Zero or more occurrences of a
Strings Matched: ε, a, aa, aaa, aaaa...

---

✅ Example 2:

RE: (a + b)*
Meaning: Any number of a's and b's in any order
Strings Matched: ε, a, b, ab, ba, aab, baba, ...

---

✅ Example 3:

RE: ab*
Meaning: An a followed by zero or more bs
Strings Matched: a, ab, abb, abbb, ...

---

✅ Example 4:

RE: a(b + c)
Meaning: a followed by either b or c
Strings Matched: ab, ac

---

✅ Example 5:

RE: (a + b)*abb
Meaning: All strings over a and b that end with abb
Strings Matched: abb, aabb, bababb, aaabb, babababb

Regular Expressions Vs Languages

The symbols of the regular expressions are distinct from those of the languages. These symbols are given below −

Operators in Regular Expression

There are two binary operations on regular expressions (+ and ·) and one unary operator (*)

These are closely associated with the union, product and closure operations on the corresponding languages.

Example 2

The regular expression a + bc* is basically shorthand for the regular language {a} ∪ ({b} · ({c}*)).

Find the language of the given regular expression.

 

Properties of Regular Expressions

All the properties held for any regular expressions R, E, F and can be verified by using properties of languages and sets.

1)Additive (+) Properties

The additive properties of regular expressions are as follows −

R + E = E + R

R + ∅ = ∅ + R = R

R + R = R

(R + E) + F = R + (E + F)

2)Product (.) Properties

The product properties of regular expressions are as follows −

R∅ = ∅R = ∅

R∧ = ∧R = R

(RE)F = R(EF)

3)Distributive Properties

The distributive properties of regular expressions are as follows −

R(E + F) = RE + RF

(R + E)F = RF + EF

 

4)Closure Properties

The closure properties of regular expressions are as follows −

∅* = ∧ * = ∧

R* = R*R* = (R*)* = R + R*

R* = ∧ + RR* = (∧ + R)R*

RR* = R*R

R(ER)* = (RE)*R

(R + E)* = (R*E*)* = (R* + E*)* = R*(ER*)*

All the properties can be verified by using the properties of languages and sets.

Example 1

Show that,

(∅ + a + b)* = a*(ba*)*

Using the properties above −

(∅ + a + b)* = (a + b)* (+ property)

= a*(ba*)* (closure property)

Example 2

Show that,

∧ + ab + abab(ab)* = (ab)*

Using the properties above −

∧ + ab + abab(ab)* = ∧ + ab(∧ + ab(ab)*)

= ∧ + ab((ab)*) (using R* = ∧ + RR*)

= ∧ + ab(ab)*= (ab)* (using R* = ∧ + RR* again)

Regular Expressions and Regular Set

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 as and bs of any length including the null string. So L = { ε, a, b, aa , ab , bb , ba, aaa.}
(a+b)*abb	Set of strings of as and bs ending with the string abb. So L = {abb, aabb, babb, aaabb, ababb, ..}
(11)*	Set consisting of even number of 1s including empty string, So L= {ε, 11, 1111, 111111, .}
(aa)*(bb)*b	Set of strings consisting of even number of as followed by odd number of bs , so L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ..}
(aa + ab + ba + bb)*	String of as and bs 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, ..}

 

2.2)REGULAR LANGUAGES

🔹 1. Regular Languages

✅ Definition:

A Regular Language is a set of strings that can be:

• Described by a Regular Expression
• Accepted by a Finite Automaton (DFA or NFA)

These languages are the simplest in the Chomsky hierarchy.

---

✅ Examples of Regular Languages:

Regular Expression	Language Description
a*	All strings with zero or more as
(a + b)*	All strings made up of a and b
a(bc)*	Strings like a, abc, abcbc, etc.
(a + b)*abb	All strings over a and b ending in abb

---

✅ Closure Properties:

Regular languages are closed under:

• Union (L1 ∪ L2)
• Concatenation (L1L2)
• Kleene star (L*)
• Intersection (L1 ∩ L2)
• Complementation
• Difference
• Reversal

---

✅ Decision Properties:

decide the following for regular languages:

• Emptiness: Is the language empty?
• Finiteness: Does it contain only a finite number of strings?
• Membership: Is a given string in the language?
• Equivalence: Are two regular expressions the same?

Closure Properties of Regular Languages

🔷 What is "Closure"?

A class of languages (like regular languages) is said to be closed under an operation if applying that operation on regular languages always produces another regular language.

Regular languages are closed under many operations, which makes them powerful and easy to manipulate.

---

✅ Closure Properties of Regular Languages

Operation	Closed?	Description
Union (L1 ∪ L2)	✅ Yes	The union of two regular languages is also regular
Concatenation (L1L2)	✅ Yes	The concatenation of two regular languages is regular
Kleene Star (L*)	✅ Yes	The repetition (zero or more times) of a regular language is regular
Intersection (L1 ∩ L2)	✅ Yes	The common strings between two regular languages form a regular language
Complement (¬L)	✅ Yes	All strings not in the regular language still form a regular language
Difference (L1 - L2)	✅ Yes	All strings in L1 but not in L2 form a regular language
Reversal (L^R)	✅ Yes	The reverse of all strings in a regular language is also regular
Substitution	✅ Yes	Replacing symbols in a regular language with strings from other regular languages
Homomorphism	✅ Yes	Replacing each symbol with a string preserves regularity
Inverse Homomorphism	✅ Yes	Pre-images of homomorphisms preserve regularity

---

🔍 Examples for Each Operation

1. Union

If
L1 = {a, ab} and L2 = {b, ba}
Then
L1 ∪ L2 = {a, ab, b, ba} → Regular

---

2. Concatenation

L1 = {a} and L2 = {b, bb}
L1L2 = {ab, abb} → Regular

---

3. Kleene Star

L = {a}
L* = {ε, a, aa, aaa, ...} → Regular

---

4. Intersection

L1 = (a + b)*a (strings ending in 'a')
L2 = (a + b)*b (strings ending in 'b')
L1 ∩ L2 = ∅ → Still regular

---

5. Complement

If L = {strings that contain at least one a}
Then ¬L = {strings that contain no a} → {b, bb, ...} → Regular

---

6. Difference

L1 = (a + b)* (all strings)
L2 = a* (only strings with a's)
L1 - L2 = all strings not consisting of only a's → Regular

---

7. Reversal

L = {ab, ba}
L^R = {ba, ab} → Regular

 

2.3) FINITE AUTOMATA

A finite automata is an abstract machine used to model computation. It consists of a finite number of states and operates on input symbols to transition between these states based on a set of rules.

To represent the finite automata, we need 5 tuples −

M=(Q,Σ,δ,q0,F)

where −

• Q − A finite, non-empty set of states.
• Σ − A finite, non-empty set of input alphabets (symbols).
• δ − The transition function, which maps into .
• q0 − The initial state, which is an element of .
• F − A subset of representing the set of final states.

Components of 5-Tuple

Following are the components of the 5-Tuple −

• States (Q) − Q is a finite, non-empty set of states. Each state represents a unique condition or configuration of the system.
• Input Alphabets (Σ) − Σ is the finite, non-empty set of input symbols that the automaton reads to determine state transitions.
• Transition Function (δ) − δ is a set of functions that defines how the automaton transitions from one state to another based on the current state and input symbol. It can be expressed as: δ:Q×Σ→Q.
• Initial State (q0) − q0 is the initial state from which the automaton starts its computation. It belongs to the set.
• Final States (F) − F is a subset of containing one or more final states. These states signify the acceptance of the input string by the automaton.

Example of Involving an Elevator System with Three Floors

To better understand finite automata, let's consider a simple example involving a lift (elevator) system with three floors: Ground floor, First floor, and Second floor.

The lift can move between these floors based on user input. To design the automata, we need to first define the states, then the alphabets, transition, initial, state and the final state. Let's discuss each of them one by one −

• States (Q):
• Q0: Ground floor
• Q1: First floor
• Q2: Second floor
• Input Alphabets (Σ):
• 0: Go to the ground floor
• 1: Go to the first floor
• 2: Go to the second floor
• Transition System − The transition system of the lift can be represented as a directed graph.

ü  In this directed graph, circles denote states (Q0, 1, Q1). Directed edges represent transitions based on input symbols.

ü  The transition system of the lift can be visualized as the above mentioned directed graph with three states: Q0 (ground floor), Q1 (first floor), and Q2 (second floor).

ü  Each state is represented by a circle. The initial state, Q0, is indicated by an inward arrow. Transitions between states are depicted by directed edges based on input symbols.

• From 0, an input of 0 leads to Q0 (self-loop), an input of 1 leads to Q1, and an input of 2 leads to Q2.
• From 1, an input of 0 transitions to Q0, an input of 1 remains in Q1 (self-loop), and an input of 2 transitions to Q2.
• From 2, an input of 0 transitions to Q0, an input of 1 transitions to Q1, and an input of 2 remains in Q2 (self-loop).
• The final state, 2, is represented by a double circle.

Transition Diagram

It is a directed graph associated with the vertices of the graph corresponding to the state of finite automata.

• {0,1}: Inputs
• q1: Initial state
• q2: Intermediate state
• qf: Final state

Transition Table

Present State	Input	Next State
Q0	0	Q0
Q0	1	Q1
Q0	2	Q2
Q1	0	Q0
Q1	1	Q1
Q1	2	Q2
Q2	0	Q0
Q2	1	Q1
Q2	2	Q2

TYPES OF FINITE AUTOMATA

ü  Finite automata is an abstract computing device. It is a mathematical model of a system with discrete inputs, outputs, states and a set of transitions from state to state that occurs on input symbols from the alphabet Σ.

Formal Definition of Finite Automata

Finite automata is defined as a 5-tuples −

M=(Q,Σ,δ,q0,F)

where,

• Q − A finite, non-empty set of states.
• Σ − A finite, non-empty set of input alphabets (symbols).
• δ − The transition function, which maps into .
• q0 − The initial state, which is an element of .
• F − A subset of representing the set of final states.

Types of Finite Automata

The different types of Finite Automata are as follows −

• Finite Automata without output −
• Deterministic Finite Automata (DFA)
• Non-Deterministic Finite Automata (NFA or NDFA)
• Non-Deterministic Finite Automata with epsilon moves (e-NFA or e-NDFA)
• Finite Automata with Output −
• Moore Machine
• Mealy Machine

Deterministic Finite Automata (DFA)

A Deterministic Finite automata is defined as a 5-tuples.

M=(Q,Σ,δ,q0,F)

where,

• Q: Finite set called states.
• Σ: Finite set called alphabets.
• δ: Q × Σ → Q is the transition function.
• q0 ∈ Q is the start or initial state.
• F: Final or accept state.

Non-deterministic Finite Automata (NFA)

NFA also have five states which are same as DFA, but with different transition function, as shown follows −

δ:Q×Σ→2Q

Non-deterministic finite automata is defined as a 5 tuple,

M=(Q,Σ,δ,q0,F)

Where,

• Q: Finite set of states
• Σ: Finite set of the input symbol
• q0: Initial state
• F: Final state
• δ: Transition function: Q X Σ -> 2Q

Mealy Machine

The Mealy machine described by 6 tuples (Q, q0, Σ, O, δ, λ')

Where,

• Q: Finite set of states
• q0: Initial state of machine
• Σ: Finite set of input alphabet
• O: Output alphabet
• δ: Transition function where Q × Σ → Q
• λ': Output function where Q × Σ →O

Moore Machine

Moore machine described by 6 tuples (Q, q0, Σ, O, δ, λ)

where,

• Q: Finite set of states
• q0: Initial state of machine
• Σ: Finite set of input symbols
• O: Output alphabet
• δ: Transition function where Q × Σ → Q
• λ: Output function where Q → O

Example: DFA for Regular Expression (a + b)abb

This DFA accepts strings ending in abb.

→ q0 —a→ q0

   q0 —b→ q0

   q0 —a→ q1

   q1 —b→ q2

   q2 —b→ q3 (Accepting)

Applications of Finite Automata

The following table summarizes the key applications of finite automata −

Application Area	Description
Language Processing	Used in email filters and smart assistants like Alexa, Siri, and Google Assistant.
Compiler Construction	Translates high-level programming languages into machine code.
Computer Networks	Underlies the design of network protocols such as HTTP and HTTPS.
Video Games	Manages game mechanics and AI, as seen in games like Warcraft 3.
Digital Circuit Design	Designs digital circuits in devices such as fans, refrigerators, and washing machines.
Biomedical Problem Solving	Utilized in medical imaging technologies like X-ray diffraction and tomography.

 

1)Finite Automata in Language Processing

One of the most important applications of automata is "language processing". It involves the interaction between human language and computational systems. We can further discuss the key applications in this domain −

• Email Filters − Finite automata help to differentiate between legitimate emails and the spams, ensuring users only see relevant messages.
• Smart Assistants − Devices like Amazon's Alexa, Microsoft's Cortana, Apple's Siri, and Google Assistant and other voice assistance tools use finite automata algorithms for interpreting and responding to user inputs.

2)Finite Automata in Compiler Construction

ü  After language processing, it is necessary to talk about compilers. In compiler construction, finite automata are crucial for translating high-level programming languages into machine code. FA enables computers to execute complex programs by converting them into a language they understand.

3)Finite Automata in Computer Networks

ü  There are some great applications in computer networks also. These are essential in developing protocols for computer networks.

Example

·       Network Protocols − Protocols such as HTTP and HTTPS rely on finite automata for managing data transmission and communication across networks, ensuring data is transferred accurately and securely.

4)Finite Automata in Video Games

ü  Video games often utilize finite automata for managing complex algorithms and game mechanics. For instance: The algorithm design for games like Warcraft 3, they use finite automata to create advanced AI behaviours, enhancing the player's gaming experience.

5)Finite Automata in Digital Circuit Design

ü  Finite automata are used in designing digital circuits as well, which are fundamental components of electronic devices. In circuit designing, everyday devices like fans, refrigerators, and washing machines incorporate digital circuits designed using finite automata, ensuring their efficient and reliable operation.

6)Finite Automata in Biomedical Problem Solving

ü  In biomedical fields, the finite automata also play a great role, particularly in medical imaging, where technologies such as X-ray diffraction and X-ray tomography utilize finite automata algorithms to produce accurate diagnostic images.