From finite automata to regular grammars

(1)

Formal Languages, Automata and Compilers

Lecure 4

2020-21

(2)

Curs 4

1 Grammars of type 3 and finite automata

2 Closure properties for type 3 languages

3 Regular Expressions

4 The automaton equivalent to a regular expression Algorithm

(3)

Grammars of type 3 and finite automata

Lecture 4

(4)

From regular grammars to finite automata

For any regular grammar G (in normal form) there exists a nondeterministic finite automaton A such that L(A) =L(G):

In grammar G In automaton A

T Σ =T

N Q=N∪ {f},F ={f}

S q₀=S

q →ap p∈δ(q,a) q→a f ∈δ(q,a) if S→ǫ add S to F

(5)

From finite automata to regular grammars

For any deterministic finite automaton there exists a regular grammar G such that L(A) =L(G):

In automaton A In grammar G

Σ T = Σ

Q N =Q

q₀ S=q₀

δ(q,a) =p q→ap

δ(q,a)∈F q →a

if q₀∈F add rule q₀→ǫ

(6)

Closure properties for type 3 languages

Lecture 4

(7)

Closure under intersection

If L₁,L₂∈ L3, then L₁∩L₂∈ L3

Let A₁= (Q1,Σ1, δ₁,q₀₁,F₁)and A₂= (Q2,Σ2, δ₂,q₀₂,F₂)be deterministic automata such that L₁=L(A1)and L₂=L(A2).

The deterministic automaton A that recognizes L₁∩L₂: A= (Q₁×Q₂,Σ₁∩Σ₂, δ,(q₀₁,q₀₂),F₁×F₂) δ((q1,q₂),a)) = (q^′₁,q₂^′)iff:

δ₁(q1,a) =q₁^′ δ₂(q2,a) =q₂^′

(8)

Closure under complement and set difference operations

If L∈ L3then L= (Σ^∗\L)∈ L3

Let A= (Q,Σ, δ,q₀,F)be a finite automaton with L(A) =L. The automaton A^′ which accepts L=L(A):

A^′ = (Q,Σ, δ,q₀,Q\F)

(9)

Closure under complement and set difference operations

If L∈ L3then L= (Σ^∗\L)∈ L3

Let A= (Q,Σ, δ,q₀,F)be a finite automaton with L(A) =L. The automaton A^′ which accepts L=L(A):

A^′ = (Q,Σ, δ,q₀,Q\F)

If L₁,L₂∈ L3then L₁\L₂∈ L3:L₁\L₂=L₁∩L₂

(10)

Closure under product

Let A₁= (Q1,Σ, δ1,q₀₁,{f₁})and A₂= (Q2,Σ, δ2,q₀₂,{f₂}) automata with a single final state such that L₁=L(A₁)and L₂=L(A2).

Automaton A (withǫ-transitions) which accepts L₁·L₂: A= (Q1∪Q₂,Σ, δ,q₀₁,{f₂})

(11)

Closure under union

Let A₁= (Q1,Σ1, δ1,q₀₁,{f₁})and A₂= (Q2,Σ2, δ2,q₀₂,{f₂}) automata with a single final state such that L₁=L(A₁)and L₂=L(A2).

Automaton A (withǫ-transitions) which accepts L₁∪L₂: A= (Q1∪Q₂∪ {q₀,f},Σ1∪Σ2, δ,q₀,{f})

(12)

Closure under iteration

Let A= (Q,Σ, δ,q₀₁,{qf})automaton with a single final state such that L(A) =L.

Automaton A (withǫ-transitions) which accepts L^∗(=L(A)^∗):

A= (Q∪ {q0,f},Σ, δ^′,q₀,{f})

(13)

Regular Expressions

Lecture 4

(14)

Regular Expressions

Regular expressions - definition

Definition 1

IfΣis an alphabet, then a regular expression overΣcan be defined by induction:

∅,ǫ, a (a∈Σ) are regular expressions which describe the languages: ∅,{ǫ},{a}.

If E , E₁, E₂are regular expressions, then:

(E1|E2)is a regular expression which describes the language L(E1)∪L(E 2)

(E1·E2)is a regular expression which describes the language L(E1)L(E2)

(E^∗)is a regular expression which describes the language L(E)^∗ The priority order for the operators is: ∗,·,|

(15)

Regular Expressions

Examples

(a|b)|(c|d)−→ {a,b,c,d}

(0|1)·(0|1)−→ {00,01,10,11}

a^∗b^∗ −→ {aⁿb^k|n,k ≥0} (a|b)^∗ −→ {a,b}^∗

(0|1|2|...|9)(0|1|2...|9)^∗ describes the set of positive integers (a|b|c|...|z)(a|b|c|...|z|0|1|2...|9)^∗describes the set of identifiers Two regular expressions E₁,E₂are equivalent, written E₁=E₂, if L(E₁) =L(E₂)

(16)

Regular Expressions

Properties

(p|q)|r =p|(q|r) (pq)r =p(qr) p|q =q|p p·ǫ=ǫ·p=p p|∅=p|p=p

∅ ·p=p· ∅=∅ p(q|r) =pq|pr (p|q)r =pr|qr ǫ|pp^∗ =p^∗ ǫ|p^∗p=p^∗

(17)

Regular Expressions

From a regular expression to a finite automaton

Theorem 1

For any regular expression E over the alphabetΣ, there existis a finite automaton (withǫ- transitions) A, such that L(A) =L(E).

Proof : structural induction

if E ∈ {∅, ǫ,a}(a∈Σ)then the corresponding automata:

(18)

Regular Expressions

Proof

E =E₁|E₂

E =E₁E₂

E =E₁^∗

(19)

Regular Expressions

Representing regular expressions as trees

Input: the regular expression E =e₀e₁. . .e_n−1 Precedence of operators:

prec(|) = 1, prec(·) = 2, prec(∗) = 3 (prec(()= 0).

Output: The corresponding tree: t.

Method: Two stacks:

STACK1 operators stack

STACK2 trees stack (contains trees for sub-expressions of the initial regular expression)

Method tree(r,tL,tR), whre r is the root node, tL the left sub-tree tR

(20)

Regular Expressions

Algorithm

i = 0;

while(i < n){ c=e_i; switch(c) {

case^′(^′: {STACK1.push(c); break;}

casesymbol (from alphabet): { STACK2.push(tree(c,NULL,NULL)); break;} caseoperator: {

while (prec(STACK1.top())>=prec(c)) build tree();

STACK1.push(c); break;

}

case^′)^′: {

do{build tree();}while(STACK1.top()!=^′(^′);

STACK1.pop(); break;

} } i++;

}

while(STACK1.not empty()) build tree();

t = STACK2.pop();

(21)

Regular Expressions

Algorithm

build tree()

op = STACK1.pop();

t1 = STACK2.pop();

switch (op) { case^′∗^′: {

new tree = tree(op, t1, NULL);

STACK2.push(new tree); break;

}

case^′|^′, ^′·^′: { t2 = STACK2.pop();

new tree = tree(op, t2, t1);

STACK2.push(new tree); break;

} }

(22)

Regular Expressions

Example

a^∗·b|a·(b|c)^∗

(23)

The automaton equivalent to a regular expression

Lecture 4

(24)

The automaton equivalent to a regular expression Algorithm

The automaton equivalent to a regular expression

E =E₁|E2

E =E₁E₂

E =E₁^∗

(25)

Remarks

for any occurrence of a symbol fromΣorǫin E , 2 states must be added in the equivalent automaton.

for every occurrence of|and∗in a regular expression E , two more states must be added

for operator·no additional states must be added

if n is the number of symbols from E and m is the number of brackets and operators·, then the number of states of the automaton equivalent to E is p=2(n−m).

(26)

Algorithm

Input: The regular expression E with n symbols, from which m are brackets and product operators;

Output: The automaton withǫ- transitions equivalent to E ;

Let generateState()be a method that generates a new state at every call (states: positive numbers greater or equal to 1)

1. Build the tree corresponding to expression E ; 2. Traverse the tree in postorder;

For every node N, two states are generated (if necessary) and assigned to N.i, N.f ; N.i, N.f , represent the initial and final states of automaton A_Nequivalent to expression E_Nwhich corresponds to the sub-tree with root N

A_Nwill be build from previously build automata, using Theorem 1

3. The initial state of the automaton is N.i, the final state is N.f , where N is the root node of the tree

(27)

Example

E =a|b^∗·c

(28)

2. Traverse the tree in post-order.

If N is the current node and L and R its children, then:

(29)

If N is labelled with a (is a leaf): N.i=generateState(), N.f=generateState(), δ(N.i,a) =N.f

(30)

If N is labelled with|:

N.i=generateState(), N.f =generateState(), δ(N.i, ǫ) ={L.i,R.i}, δ(L.f, ǫ) =N.f, δ(R.f, ǫ) =N.f

(31)

N.i=generateState(), N.f =generateState(),

δ(N.i, ǫ) ={L.i,R.i}, δ(L.f, ǫ) =N.f, δ(R.f, ǫ) =N.f If N is labelled with·:

N.i=L.i, N.f =R.f ,

δ(L.f, ǫ) =R.i

(32)

N.i=L.i, N.f =R.f ,

δ(L.f, ǫ) =R.i If N is labelled with∗(R does not exist in this case):

N.i=generateState(), N.f =generateState(), δ(N.i, ǫ) ={L.i,N.f},

δ(L.f, ǫ) ={L.i,N.f}

(33)

N.i=L.i, N.f =R.f ,

δ(L.f, ǫ) =R.i If N is labelled with∗(R does not exist in this case):

N.i=generateState(), N.f =generateState(), δ(N.i, ǫ) ={L.i,N.f},

δ(L.f, ǫ) ={L.i,N.f}

(34)

Example

E =a|b^∗·c

(35)

Example

δ a b c ǫ

1 {2} ∅ ∅ ∅

2 ∅ ∅ ∅ {10}

3 ∅ {4} ∅ ∅

4 ∅ ∅ ∅ {3,6}

5 ∅ ∅ ∅ {3,6}

6 ∅ ∅ ∅ {7}

7 ∅ ∅ {8} ∅

8 ∅ ∅ ∅ {10}

9 ∅ ∅ ∅ {1,5}

10 ∅ ∅ ∅ ∅

(36)

The correctness of the algorithm

Theorem 2

The automaton withǫ- transitions built by the algorithm is equivalent to the expression E .

Proof:

The transitions defined in the algorithm correspond to the constructions in Theorem 1.