Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Formal Language and Automata Theory (CS21004) Pattern Matching

Regular
Expressions

Regular Grammars
Soumyajit Dey Kleene Algebra

CSE, IIT Kharagpur

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Announcements and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Regular
Expressions
The slide is just a short summary Regular Grammars

Follow the discussion and the boardwork Kleene Algebra

Solve problems (apart from those we dish out in class)

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Table of Contents and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

1 Pattern Matching Pattern Matching

Regular
Expressions

Regular Grammars
2 Regular Expressions
Kleene Algebra

3 Regular Grammars

4 Kleene Algebra

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Patterns and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

A Pattern captures a family of strings (like FA) : language of the pattern Pattern Matching

a ∈ Σ : L(a) = {a} : matches a single symbol Regular

Expressions
ϵ : ϵ = {ϵ} : matches the null string Regular Grammars

ϕ : L(ϕ) = ϕ : matches empty set ϕ Kleene Algebra

♯ : L(♯) = Σ : any symbol

@ : L(@) = Σ∗ : any string
Above atomic patterns can be operated with unary ∗ , + , ¬ or connected by
∪/+, ∩, ◦ (usually not written, kept silent) to generated other valid patterns

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Patterns and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

x matches α + β if x matches either α or β : L(α + β) = L(α) ∪ L(β), Pattern Matching

similarly you have other rules Regular

Expressions
L(α ∩ β) = L(α) ∩ L(β), L(αβ) = L(α)L(β), L(¬α) = ¬L(α) = Σ∗ − L(α), Regular Grammars

Can define L(α∗ ), L(α+ ) Kleene Algebra

patterns are collections of strings over Σ, ♯, @, ϵ, ϕ, ¬, ∗ , + ,

Note 1: ϵ, ϕ and ϵ, ϕ are different. The boldfaces are symbols in the pattern
language
Note 2:‘+’ is associative over patterns

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Patterns : Applications and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Regular
Expressions
Pattern matching is an important application of FA Regular Grammars

Unix regular exps are basically patterns (Σ ??) Kleene Algebra

Unix commands ‘grep’, ‘egrep’ use FA inside their implementations

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Patterns : examples and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Regular
Expressions
Strings containing at least 3 occurrences of a : @a@a@a@
Regular Grammars
all single letters except a : # ∩ ¬a Kleene Algebra

Strings with no occurrences of a : (# ∩ ¬a)∗

Some books call patterns as regular expressions, we shall make a distinction here.

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Table of Contents and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

1 Pattern Matching Pattern Matching

Regular
Expressions

Regular Grammars
2 Regular Expressions
Kleene Algebra

3 Regular Grammars

4 Kleene Algebra

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regular Expressions and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Represents the idea of patterns as regular language (set) generators (≡ FA) in a

Pattern Matching
minimal way using only Σ, ϵ, ϕ as primitive regular expressions and operators
Regular
+, ◦, ∗ along with the option of using parenthesis (‘(’ and ‘)’) to denote operator Expressions

association. Regular Grammars

L((aa)∗ (bb)∗ b) = {a2n b 2m+1 | n, m ≥ 0}

Kleene Algebra

Regex for ‘at least one pair of consecutive 0’s’ : (0 + 1)∗ 00(0 + 1)∗
Regex for ‘no pair of consecutive 0’s’ :
(1∗ 011∗ )∗ (0 + ϵ) + 1∗ (0 + ϵ) ≡ (1 + 01)∗ (0 + ϵ) – how to reason about such
equivalence ??

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regular Expressions, Languages (sets) and FA and Automata
Theory (CS21004)

M(r) Soumyajit Dey

L(r) CSE, IIT
Kharagpur
L=φ
Pattern Matching

ǫ M(r1) Regular
L = fǫg ǫ
Expressions
ǫ
L(r1 + r2) Regular Grammars

Kleene Algebra
ǫ
a L = fag M(r2) ǫ

ǫ
M(r1) ǫ
ǫ
ǫ M(r2) L(r∗)
M(r) ǫ
ǫ
L(r1r2)

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regular Expressions, Languages (sets) and FA and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Regular
Automata for primitive regex can be combined as shown Expressions

We can give a formal method for constructing states/transitions of Regular Grammars

Kleene Algebra
combined machine from states/transitions of simpler machines
We can prove language equivalence of regex and automata generated as
above by induction on number of operators

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
DFA to Regex ?? and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT

Let states be {1, 2, · · · , n} Kharagpur

Let R(k)i,j be the Regex whose language is the set of labels of path from i Pattern Matching

Regular
to j without visiting any state with label larger than k. Expressions

Basis : R(0)i,j is basically labels of direct paths from i to j, i.e., Regular Grammars

R(0)i,j = a1 + · · · + an if δ(i, ak ) = j for 1 ≤ k ≤ n; Note R(0)i,i = ϕ if Kleene Algebra

there is no self-loop
Induction : R(k)i,j = R(k − 1)i,j + R(k − 1)i,k · (R(k − 1)k,k )∗ · R(k − 1)k,j
Overall Regex : R(n)i0 ,f1 + R(n)i0 ,f2 + · · · + R(n)i0 ,fk with i0 being the initial
state and {f1 , · · · , fk } being the set of final states.
COMPLEXITY ??? up to n3 expressions, each step creates 4 terms for one
term.

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur
Using the algorithm, NFA ⇒ DFA ⇒ Regex AND Regex ⇒ NFA ⇒ DFA
Pattern Matching
Observation : The algorithm we presented can also be devised for NFAs (check
Regular
Kozen), use ∆ instead of δ. Expressions
Alternate Method : Regular Grammars

Collapse states by allowing regex as transition labels Kleene Algebra

Derive regex which connect initial and final state pairs

Overall expression is the union of such regex

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Example of collapsing and Automata
Theory (CS21004)
Consider {w | na (w ) is even, nb (w ) is odd} : difficult to conceive regex directly. Soumyajit Dey
CSE, IIT
aa bb Kharagpur
ab
EE ba OO Pattern Matching

b a Regular
b Expressions
OE a Regular Grammars
b EO
a Kleene Algebra
a
b aa + ab(bb) ba
∗
a(bb)∗ a
EE OO b + ab(bb)∗ a
b a EE EO
b a b + a(bb) ba
∗

EO

Absence of transition between any state pair

can be thought of as φ
Note : rφ = φ r + φ = r φ∗ =λ
Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Table of Contents and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

1 Pattern Matching Pattern Matching

Regular
Expressions

Regular Grammars
2 Regular Expressions
Kleene Algebra

3 Regular Grammars

4 Kleene Algebra

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regular Grammars and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Regular Language (set) ≡ FA ≡ Regular Grammar Kharagpur

A grammar G = (V , Σ, S, P) is right linear if all productions are of the Pattern Matching

form Regular
Expressions
A → xB, A → x
Regular Grammars

where A, B ∈ V , x ∈ Σ∗ Kleene Algebra

A grammar G = (V , Σ, S, P) is left linear if all productions are of the form

A → Bx, A → x

where A, B ∈ V , x ∈ Σ∗
A regular grammar is one of the two

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Strictly Right Linear Grammars and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur
A grammar G = (V , Σ, S, P) is strictly right linear if all productions are of the
Pattern Matching
form
Regular
A → xB, A → λ Expressions

Regular Grammars
where A, B ∈ V , x ∈ Σ ∪ {λ}
Kleene Algebra
Any derivation of a word w from S has the form
S ⇒ x1 A1 ⇒ x1 x2 A2 ⇒ · · · ⇒ x1 · · · xn An ⇒ x1 · · · xn
some xi can be λ, connection with NFA ??
♠ For any right-linear grammar G there exists a strictly right-linear grammar H
such that L(G ) = L(H)

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Strictly Right Linear Grammars and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

If G is a strictly right-linear grammar, then L(G ) is regular Pattern Matching

Given G = (V , Σ, P, S), construct NFA N = (V , Σ, δ, S, F ). The set of Regular

Expressions
states is simply the set of non-terminals of G . The start state corresponds
Regular Grammars
to the start variable. Kleene Algebra
δ(A, x) = {B | A → xB ∈ P}, F = {C | C → λ ∈ P}
To show L(G ) = L(N)
L(G ) ⊆ L(N) : by induction on the structure of the derivation
L(N) ⊆ L(G ) : by induction on the structure of the computation

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Strictly Right Linear Grammars and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

If A is a regular language, then there is a strictly right-linear grammar G such Pattern Matching

that L(G ) = A Regular

Expressions
If L is regular, ∃ an NFA N = (Q, Σ, δ, q0 , F ) for L Regular Grammars

We construct a strictly right-linear grammar G = (V = Q, Σ, P, S = q0 ) Kleene Algebra

where
P = {A → xB | B ∈ δ(A, x)} ∪ {C → λ | C ∈ F }
♠ A language A is regular if and only if there is a strictly right-linear grammar
G such that L(G ) = A

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regular Grammars and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Grammar comprising both left-linear and right-linear rules will not necessarily Kharagpur
generate a regular language.
Pattern Matching
Consider
Regular
Expressions
S → 0A Regular Grammars

S → 1B Kleene Algebra

S →λ
A → S0
B → S1

The grammar generates L = {ww R | w ∈ {0, 1}∗ } which is not regular

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Table of Contents and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

1 Pattern Matching Pattern Matching

Regular
Expressions

Regular Grammars
2 Regular Expressions
Kleene Algebra

3 Regular Grammars

4 Kleene Algebra

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regex example and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Regular
Expressions

Regular Grammars

Kleene Algebra

Set of all strings without strings having two adjacent zeroes.

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Regex example and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching
The second automata is for the language Σ∗ \ “strings having more than 2 Regular
consecutive zero-s” Expressions

Regular Grammars
Regex ?
Kleene Algebra

(1 + 01 + 001)∗ (ϵ
+ 0 + 00) ≡ ((ϵ + 0 + + 0 + 00) ≡ 00)1)∗ (ϵ
((ϵ + 0)(ϵ + 0)1)∗ (ϵ + 0)(ϵ + 0)
How do we perform such equational reasoning, well there exists an underlying
algebra

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
RegEX Simplication Laws and Automata
Theory (CS21004)
Let α, β be regex; if L(α) = L(β), we say α ≡ β. ≡ is an equivalence relation. Soumyajit Dey
CSE, IIT
α + (β + γ) ≡ (α + β) + γ (1) Kharagpur

α+β ≡β+α (2) Pattern Matching

α+ϕ≡α+α≡α (3) Regular

Expressions

(αβ)γ ≡ α(βγ) (4) Regular Grammars

ϵα ≡ αϵ ≡ α
Kleene Algebra
(5)
α(β + γ) ≡ αβ + αγ (6)
(β + γ)α ≡ βα + γα (7)
αϕ ≡ ϕα = ϕ (8)
∗ ∗ ∗
ϵ + αα ≡ ϵ + α α ≡ α (9)
∗
β + αγ ≤ γ ⇒ α β ≤ γ (10)
∗
β + γα ≤ γ ⇒ βα ≤ γ (11)
Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Kleene Algebra and Automata
Theory (CS21004)

≤ in previous slide refers to subset ordering, i.e.

Soumyajit Dey
CSE, IIT

α ≤ β ⇔ L(α) ⊆ L(β) ⇔ L(α + β) = L(β) ⇔ α + β = β Kharagpur

Pattern Matching
Any algebraic structure that satisfies Eq 1 -11 is a Kleene Algebra (Named
Regular
after Stephen C. Kleene, who invented regular sets) Expressions
∗
Note that the set 2Σ (all possible subsets of Σ∗ ) with constants ϕ, ϵ and Regular Grammars

operations ∪, ·, ∗ forms a Kleene algebra, Kleene Algebra

Similarly, the family of all regular subsets, i.e. all Regular expressions (set K
say) forms a Kleene Algebra (K , +, ·, ∗, 1, 0) with operations +, · · · , ∗ and
constants 1 = ϵ, 0 = ϕ.
Note: 1a = a1 = a, a0 = 0a = 0 i.e. 1 is an identity for · and 0 is an
annihilator for ·.
Comment: This is an idempotent semiring.

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
More properties and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur
Many such relations can be derived using the rules listed. Examples:
Pattern Matching
∗ ∗ ∗
a a =a (12) Regular
Expressions
a∗∗ = a∗ (13) Regular Grammars
∗ ∗ ∗ ∗
(a b) a = (a + b) denesting rule (14) Kleene Algebra

a(ba)∗ = (ab)∗ a shifting rule (15)

∗ ∗ ∗
a = (aa) + a(aa) (16)

Arden’s Theorem: In any Kleene Algebra, a∗ b is the ≤-least solution of the

equation x = ax + b. Also, ba∗ is the solution of x = xa + b.

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Arden’s Theorem: and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Σ∗
We know that set of languages 2 under the operations union and
Regular
Expressions

concatenation is also a Kleene Algebra. Hence Ardens theorem can be stated in Regular Grammars

terms of languages as follows. Kleene Algebra

“A∗ B is the smallest language that is a solution for X in the linear equation
X = A · X ∪ B where X , A, B are sets of strings.”

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Arden’s Theorem usage: FA to RegEX and Automata
Theory (CS21004)

Soumyajit Dey
Consider the automaton given below. CSE, IIT
Kharagpur

Pattern Matching

Regular
Expressions
b
Regular Grammars

Kleene Algebra

Let the states be {0, 1, · · · , 4} left to right. Let Ai be set of strings accepted
from state i. We write
Ai = ∪{σAj | state j is accessible from state i through transition σ}. Hence,
A0 is the language of the automaton if 0 is the initial state.

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Arden’s Theorem usage: FA to RegEX and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur
We can write the following systems of Eqs.
Pattern Matching

A0 = aA1 Regular
Expressions
A1 = aA2 ∪ bA4 Regular Grammars

A2 = aA3 ∪ bA4 Kleene Algebra

A3 = ϵ ∪ aA3 ∪ bA4
A4 = ϵ ∪ bA4

ϵ is considered for equation written for accepting state (follows from definition of
Ai ).

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)
Pattern Matching Regular Expressions Regular Grammars Kleene Algebra

Formal Language
Arden’s Theorem usage: FA to RegEX and Automata
Theory (CS21004)

Soumyajit Dey
CSE, IIT
Kharagpur

Pattern Matching

Applying Arden’s Thm: A4 = = b∗ ϵ b∗ Regular

Expressions
A3 = a∗ (b + ϵ) = a∗ b ∗ Regular Grammars
A2 = a+ b ∗ ∪ b + Kleene Algebra
A1 = a(a+ b ∗ ∪ b + ) ∪ b +
A0 = a(a(a+ b ∗ ∪ b + ) ∪ b + ) = a2 a+ b ∗ ∪ a2 b + ∪ ab +
Hence, the FA has an equivalent RegEX given by a2 a+ b ∗ + a2 b + + ab +

Soumyajit Dey CSE, IIT Kharagpur Formal Language and Automata Theory (CS21004)