[PDF] Chapter 3 Regular grammars Example: programming languages are defined

View - Download Chapter 3 Regular grammars

Previous PDF

Next PDF

Chapter 3

Regular grammars

59

3.1 Introduction

Other view of the concept of language:

not the formalization of the notion of eective procedure, but set of words satisfying a given set of rules

Origin : formalization of natural language.

60

Example

aphraseis of the formsubject verb asubjectis apronoun apronounisheorshe a verb issleepsorlistens

Possible phrases:

1.he listens

2.he sleeps

3.she sleeps

4.she listens

61

Grammars

Grammar:generativedescription of a language

Automaton:analyticaldescription

Example: programming languages are dened by a grammar (BNF), but recognized with an analytical description (the parser of a compiler), Language theory establishes links between analytical and generative language descriptions. 62

3.2 Grammars

A grammar is a 4-tupleG= (V;;R;S), where

Vis an alphabet,

Vis the setterminal symbols(V is the set ofnonterminal symbols), R(V+V) is a nite set ofproduction rules(also called simply rules or productions),

S2V is thestart symbol.

63

Notation:

Elements ofV :A;B;:::

Elements of :a;b;:::.

Rules (;)2R:!or!G.

The start symbol is usually written asS.

Empty word:".

64

Example :

V=fS;A;B;a;bg,

=fa;bg,

R=fS!A;S!B;B!bB;A!aA;A!";B!"g,

Sis the start symbol.

65

Words generated by a grammar: example

aaaais in the language generated by the grammar we have just described: S

AruleS!A

aA A!aA aaA A!aA aaaA A!aA aaaaA A!aA aaaa A!" 66

Generated words: denition

LetG= (V;;R;S) be a grammar andu2V+; v2Vbe words. The wordvcan be derived in one step fromubyG(notationu)Gv) if and only if: u=xu0y(ucan be decomposed in three partsx,u0andy; the partsx andybeing allowed to be empty), v=xv0y(vcan be decomposed in three partsx,v0andy), u0!Gv0(the rule (u0;v0) is inR). 67
LetG= (V;;R;S) be a grammar andu2V+; v2Vbe words. The wordvcan be derived in several steps fromu(notationu)Gv) if and only if9k0 andv0:::vk2V+such that u=v0, v=vk, vi)Gvi+1for 0i < k. 68
Words generated by a grammarG: wordsv2(containing only terminal symbols) such that S )Gv: The language generated by a grammarG(writtenL(G)) is the set

L(G) =fv2jS)Gvg:

Example :

The language generated by the grammar shown in the example above is the set of all words containing either onlya's or onlyb's. 69

Types of grammars

Type 0:no restrictions on the rules.

Type 1:Context sensitivegrammars.

The rules

satisfy the condition jj jj:

Exception: the rule

S!" is allowed as long as the start symbolSdoes not appear in the right hand side of a rule. 70

Type 2:context-freegrammars.

Productions of the form

A! whereA2V and there is no restriction on.

Type 3:regulargrammars.

Productions rules of the form

A!wB A!w whereA;B2V andw2. 71

3.3 Regular grammars

Theorem:

A language is regular if and only if it can be generated by a regular grammar. A. If a language is regular, it can be generated by a regular grammar.

IfLis regular, there exists

M= (Q;;;s;F)

such thatL=L(M). FromM, one can easily construct a regular grammar

G= (VG;G;SG;RG)

generatingL. 72

Gis dened by:

G= ,

VG=Q[,

SG=s,

RG=(A!wB;for all(A;w;B)2

A!"for allA2F)

73
B. If a language is generated by a regular grammar, it is regular. Let

G= (VG;G;SG;RG)

be the grammar generatingL. A nondeterministic nite automaton acceptingLcan be dened as follows: Q=VGG[ ffg(the states ofMare the nonterminal symbols ofG to which a new statefis added), = G, s=SG,

F=ffg,

=((A;w;B);for allA!wB2RG(A;w;f);for allA!w2RG) 74

3.4 The regular languages

We have seen four characterizations of the regular languages: 1. regula rexp ressions, 2. deterministic nite automata, 3. nondeterministic nite automata, 4. regula rgramma rs. 75

Properties of regular languages

LetL1andL2be two regular languages.

L1[L2is regular.

L1L2is regular.

L1is regular.

LR1is regular.

L1=

L1is regular.

L1\L2is regular.

76
L

1\L2regular ?

L

1\L2=L1

[L2 Alternatively, ifM1= (Q1;; 1;s1;F1) acceptsL1andM2= (Q2;;2;s2; F

2) acceptsL2, the following automaton, acceptsL1\L2:

Q=Q1Q2,

((q1;q2);) = (p1;p2) if and only if1(q1;) =p1and2(q2;) =p2, s= (s1;s2),

F=F1F2.

77
Let be the alphabet on whichL1is dened, and let: !0be a function from to another alphabet 0. This fonction, called aprojection functioncan be extended to words by applying it to every symbol in the word,i.e.forw=w1:::wk2, (w) =(w1):::(wk).

IfL1is regular, the language(L1) is also regular.

78

Algorithms

Les following problems can be solved by algorithms for regular languages: w2L? L=;?

L= ? (L=;)

L1L2? (L2\L1=;)

L1=L2? (L1L2andL2L1)

79

3.5 Beyond regular languages

Many languages are regular,

But, all languages cannot be regular for cardinality reasons. We will now prove, using another techniques that some specic languages are not regular. 80

Basic Observations

1. All nite languages (including only a nite numb erof w ords)a re regular. 2. A non regula rlanguage must thus include an innite numb erof w ords. 3. If a language includes an innite numb erof w ords,there is no b ound on the size of the words in the language. 4. Any regula rlanguage is accepted b ya nite automaton that has a given number numbermof states. 81

5.Consider an innite regula rlanguage and an automaton with mstates

accepting this language. For any word whose length is greater thanm, the execution of the automaton on this word must go through an identical stateskat least twice, a nonempty part of the word being read between these two visits tosk.ssssksskssfx u y 6. Consequently ,all w ordsof the fo rmxuyare also accepted by the automaton and thus are in the language. 82

The "pumping" lemmas (theorems)

First version

LetLbe an innite regular language. Then there exists wordsx;u;y2, withu6="such thatxuny2L8n0.

Second version :

LetLbe a regular language and letw2Lbe such thatjwj jQjwhereQ is the set of states of a determnistic automaton acceptingL. Then

9x;u;y, withu6="andjxuj jQjsuch thatxuy=wand,8n; xuny2L.

83

Applications of the pumping lemmas

The langage

a nbn is not regular. Indeed, it is not possible to nd wordsx;u;ysuch that xu ky2anbn8kand thus the pumping lemma cannot be true for this language. u2a:imp ossible. u2b:imp ossible. u2(a[b)(a[b) :imp ossible. 84

The language

L=an2 is not regular. Indeed, the pumping lemma (second version) is contradicted. Letm=jQjbe the number of states of an automaton acceptingL. Consideram2. Sincem2m, there must existx,uandysuch that jxuj mandxuny2L8n. Explicitly, we have x=ap0pm1; u=aq0< qm; y=arr0: Consequentlyxu2y62Lsincep+ 2q+ris not a perfect square. Indeed, m

2< p+ 2q+rm2+m <(m+ 1)2=m2+ 2m+ 1:

85

The language

L=fanjnis primeg

is not regular. The rst pumping lemma implies that there exists constantsp,qandrsuch that8k xu ky=ap+kq+r2L; in other words, such thatp+kq+ris prime for allk. This is impossible since fork=p+ 2q+r+ 2, we have p+kq+r= (q+ 1)|{z} >1(p+ 2q+r)|{z} >1; 86

Applications of regular languages

Problem :To nd in a (long) character stringw, all ocurrences of words in the language dened by a regular expression. 1.

Consider the re gularexp ression= .

2. Build a nondeterministic automaton accepting the language dened b y 3. F romthis automaton, build a deterministicautomatonA. 4. Simulate the exe cutionof the automaton Aon the wordw. Whenever this automaton is in an accepting state, one is at the end of an occurrence inwof a word in the language dened by. 87

Applications of regular languages II:

handling arithmetic A number written in baseris a word over the alphabetf0;:::;r1g (f0;:::;9gin decimal,f0;1gen binary).

The number represented by a wordw=w0:::wlis

nb(w) =Pli=0rlinb(wi) Adding leading 0's to the representation of a number does not modify the represented value. A number thus has a innite number of possible representations. Number encodings are read most signicant digit rst, and all possible encodings will be taken into account. Exemple:The set of binary representations of 5 is the language 0 101.
88
Which sets of numbers can be represented by regular languages?

Finite sets.

The set of multiples of 2 is represented by the language (0[1)0. The set of powers of 2 is represented by the language 010, but is not representable in base 3. The set of multiples of 3 is represented by the following automaton.0 11 01 0 89

Set of numbers represented by regular languages

(continued) The set of numbersx5 is represented by the automaton0 0 1 1 10 0;1

0;10;1

More generally, one can represent sets of the formfaxjx2Ngor fxajx2Ngfor any given value ofa. 90

Set of numbers represented by regular languages

(continued II) Combining the two types of sets: sets of the formfax+bjx2Ng, for any givenaandb.

Union of such sets: theultimately periodic sets.

Intersection and complementation add nothing more. The only sets that can be represented in all bases are the ultimately periodic sets. 91

Representing vectors of numbers

Each number is represented by a word, and bits in identical positions are read together.

Example:

{the vector (5;9) is encoded by the word (0;1)(1;0)(0;0)(1;1) dened over the alphabetf0;1g f0;1g. {The set of binary encodings of the vector (5;9) is (0;0)(0;1)(1;0) (0;0)(1;1). 92
Which sets of number vectors can be represented by regular languages? The set of binary encodings of the vectors (x;y) such thatx=yis accepted by the automaton> (0;0) (1;1) 93

Vectors (x;y) such thatx < y>

(0;0)(0 ;0);(0;1);(1;0);(1;1) (0;1) (1;1)

Three-dimentional vectors (x;y;z) such thatz=x+y>

(0;0;1) (1;1;0)(0;0;0);(0;1;1);(1;0;1)(1 ;0;0);(0;1;0);(1;1;1) 94

Denable sets of number vectors (continued)

Intersection, union, complement of representable sets (closure properties of regular languages). Modifying the number of dimensions: projection and the inverse operation. Remark:projection does not always preserve the determinism of the automaton. Example:f(x;z)j 9y x+y=zg(xz).>>(0;0);(0;1);(1;1)(1 ;0);(0;0);(1;1) (0;1) (1;0) 95
Adding a dimension to the previous automaton yields>> (1;0;0)(1;1;0)(0;1;1) (0;0;1)(1;1;0);(0;1;0);(1;1;1) (0;0;0);(0;0;1);(1;0;1) which is not equivalent to the automaton to which projection was applied. 96

Representable sets of vectors: conclusions

Linear equality and inequality constraints

Example:an automaton forx+ 2y= 5 can be obtained by combing the automata for the following constraints: z 1=y z

2=y+z1

z3=x+z2 z3= 5:

There exists also a more direct construction.

97
Representable vector sets: conclusions (continued)

Boolean combinations of linear constraints

Existential quantication can be handled with projection (9x).

For universal quantication, one uses8xf :9:f

Example:It is possible to build an automaton accepting the representations of the vectors (x;y) satisfying the arithmetic constraint

8u9t[(2x+ 3y+t4u= 5)_(x+ 5y3t+ 2u= 8)]

This is Presburger arithmetic, which corresponds exactly to the sets representable by automata in all bases. 98
quotesdbs_dbs14.pdfusesText_20

[PDF] regular octagonal prism volume

[PDF] regular overtime

[PDF] regular solution

[PDF] regular solution model

[PDF] regular solution model interaction parameter

[PDF] regular solution theory equation

[PDF] regular verb in pdf

[PDF] regular verbs list pdf

[PDF] regularization and optimization

[PDF] regulating body of open and distance education in india

[PDF] regulating body of open and distance learning

[PDF] regulation of cryptocurrency around the world

[PDF] regulatory guidelines for software medical devices a lifecycle approach

[PDF] regulatory takings flowchart

[PDF] relâche scolaire 2020 laval