• Nu S-Au Găsit Rezultate

# From finite automata to regular grammars

N/A
N/A
Protected

Share "From finite automata to regular grammars"

Copied!
36
0
0

Text complet

(1)

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

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

(4)

Grammars of type 3 and finite automata

### 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 q0=S

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

(5)

Grammars of type 3 and finite automata

### 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

q0 S=q0

δ(q,a) =p qap

δ(q,a)F qa

(6)

Closure properties for type 3 languages

### Lecture 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

(7)

Closure properties for type 3 languages

### Closure under intersection

If L1,L2∈ L3, then L1L2∈ L3

Let A1= (Q11, δ1,q01,F1)and A2= (Q22, δ2,q02,F2)be deterministic automata such that L1=L(A1)and L2=L(A2).

The deterministic automaton A that recognizes L1L2: A= (Q1×Q21∩Σ2, δ,(q01,q02),F1×F2) δ((q1,q2),a)) = (q1,q2)iff:

δ1(q1,a) =q1 δ2(q2,a) =q2

(8)

Closure properties for type 3 languages

### Closure under complement and set difference operations

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

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

A = (Q,Σ, δ,q0,Q\F)

(9)

Closure properties for type 3 languages

### Closure under complement and set difference operations

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

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

A = (Q,Σ, δ,q0,Q\F)

If L1,L2∈ L3then L1\L2∈ L3:L1\L2=L1L2

(10)

Closure properties for type 3 languages

### Closure under product

Let A1= (Q1,Σ, δ1,q01,{f1})and A2= (Q2,Σ, δ2,q02,{f2}) automata with a single final state such that L1=L(A1)and L2=L(A2).

Automaton A (withǫ-transitions) which accepts L1·L2: A= (Q1Q2,Σ, δ,q01,{f2})

(11)

Closure properties for type 3 languages

### Closure under union

Let A1= (Q11, δ1,q01,{f1})and A2= (Q22, δ2,q02,{f2}) automata with a single final state such that L1=L(A1)and L2=L(A2).

Automaton A (withǫ-transitions) which accepts L1L2: A= (Q1Q2∪ {q0,f},Σ1∪Σ2, δ,q0,{f})

(12)

Closure properties for type 3 languages

### Closure under iteration

Let A= (Q,Σ, δ,q01,{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},Σ, δ,q0,{f})

(13)

Regular Expressions

### Lecture 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

(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 , E1, E2are 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}

ab −→ {anbk|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 E1,E2are equivalent, written E1=E2, if L(E1) =L(E2)

(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 ǫ|pp=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 =E1|E2

E =E1E2

E =E1

(19)

Regular Expressions

### Representing regular expressions as trees

Input: the regular expression E =e0e1. . .en−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=ei; 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

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

(24)

The automaton equivalent to a regular expression Algorithm

### The automaton equivalent to a regular expression

E =E1|E2

E =E1E2

E =E1

(25)

The automaton equivalent to a regular expression Algorithm

### 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

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)

The automaton equivalent to a regular expression Algorithm

### 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 ANequivalent to expression ENwhich corresponds to the sub-tree with root N

ANwill 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)

The automaton equivalent to a regular expression Algorithm

### Example

E =a|b·c

(28)

The automaton equivalent to a regular expression Algorithm

2. Traverse the tree in post-order.

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

(29)

The automaton equivalent to a regular expression Algorithm

2. Traverse the tree in post-order.

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

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

(30)

The automaton equivalent to a regular expression Algorithm

2. Traverse the tree in post-order.

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

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

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)

The automaton equivalent to a regular expression Algorithm

2. Traverse the tree in post-order.

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

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

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 If N is labelled with·:

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

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

(32)

The automaton equivalent to a regular expression Algorithm

2. Traverse the tree in post-order.

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

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

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 If N is labelled with·:

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)

The automaton equivalent to a regular expression Algorithm

2. Traverse the tree in post-order.

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

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

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 If N is labelled with·:

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)

The automaton equivalent to a regular expression Algorithm

### Example

E =a|b·c

(35)

The automaton equivalent to a regular expression Algorithm

### 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 automaton equivalent to a regular expression Algorithm

### 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.

Referințe

DOCUMENTE SIMILARE

f ∗ (t,. Fie F s¸i G dou˘a polinoame de grad cel mult n, iar f, g – formele lor n-polare cores- punz˘atoare. ˆIn acest scop, construim, mai ˆıntˆai, un s¸ir de

o Pentru c516torii care au fost in alte localitati din regiunile Lombardia, Veneto si regiunea Piemonte, decat cele mai sus mentionate, se recomandd

Deºi înscrierea pe internet ºi obþinerea locului de cazare într-un campus destul de central din Paris mi-au fost confirmate ºi mi s-a spus sã fiu prezen- tã pe 3 septembrie

Et, bien sûr, j’ai essayé de décrypter les mots de l’auteur et le sens bien particulier que leur donne Chitra Banerjee Divakaruni, en étant particulièrement attentive aux

Most of the problems regarding the methods of approximating the solutions of nonlinear equations in abstract spaces lead, as is well known, to solving of linear systems in R n , n ∈

In what follows we shall prove that for the class of continuous functions having also a continuous derivative, the condition of boundedness of the se- quence |a 1 |+...+|a n n | n∈.

In the very recent paper , Strichartz investigated the behaviour of the arclengths of the graphs Γ(S N (f )) of the partial sums S N (f ) of the Fourier series of a piecewise

l'his section colrtajus the main result ol the paper Tornulated i-n'-[heo- retn =-.2.. Initial a¡tl hountlar¡i

Thermal stability of all the samples was studied by means of thermogravimetric analysis and the surface morphology of the NIPAAM hydrogel is compared with that of

Résumé: Le sourire, comme le rire, tous deux des expressions humaines, non-animales, se détachent comme des paradigmes abstraits d’un sourire sans corps ou sans

The synthesized dark yellow-green Cr x O y films were actually chromium oxide, Cr 5 O 12 nanocrystals of size 12.02nm; however, as precursor concentration was increased, Cr 8 O 21

A STUDY OF THE OPTICAL PROPERTIES OF UN-DOPED AND POTASH DOPED LEAD CHLORIDE CRYSTAL IN SILICA GEL..

The PL spectra collected from room temperature to 77K by cooling have shown one violet prominent emission at 408.93nm, one blue prominent emissions at 422.87nm and one very

16 Véase Carlos Bousoño, “Iraţíonalitatea în poezia contemporană” (en Teoria expresiei poetice, Bucureşti, Univers, 1975, cap. 17 Esta palabra, que aparece

Sarrebruck : Editions Universitaires Européennes (EUE).. moins intéressé par ce que les approches fonctionnalistes ont de particulier comparativement aux autres

O varietate de dimensiunea n este un spatiu cu proprietatea ca langa fiecare punct ne putem misca in n directii (n grade de libertate)?. n=0:

[r]

Definit¸ia 15 Un proces stochastic X = {X n | n ∈ I} este o familie de variabile aleatoare, definite pe un spat¸iu comun de probabilitate (Ω, F, P ) , indexate dup˘a o mult¸ime

Thus we obtain a generalization for 7r-solvable groups of some of O R E’s theorems from  given for solvable groups and being of special interest in the formation

Deocamdată domnul ofiţer Roos, aflat pentru a doua oară în aceste părţi ale lumii – prima oară fusese în 1883 –, îşi sfătuieşte cititorii care au de gând să-şi în

Astfel `ncât nu e nicio f\râm\ de exagerare `n asocierea lui Bernard Pivot – unul dintre cei mai influen]i critici literari, ga- zetari culturali [i vedete mediatice din

Orice şir mărginit, cu elemente din R, conţine cel puţin un subşir convergent ( Altfel spus, mulţimea punctelor limită ale oricărui şir mărginit de numere reale este nevidă

Formazan: Imine compounds comprise (-HC=N-) the azomethine group (6) , when they bond directly to the group (- N=N-) contained in the Azo dyes (3-7) , resulting in compounds