[PDF] [PDF] Regular expressions and Kleenes theorem - Informatics 2A: Lecture 5

View - Download [PDF] Regular expressions and Kleenes theorem - Informatics 2A: Lecture 5

Previous PDF

Next PDF

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraRegular expressions and Kleene's theorem

Informatics 2A: Lecture 5

John Longley

School of Informatics

University of Edinburgh

jrl@inf.ed.ac.uk

29 September 2016

1/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebra1More closure properties of regular languages

Operations on languages

-NFAsClosure under concatenation and Kleene star

2Regular expressions

Regular expressions

From regular expressions to regular languages

3Kleene's theorem and Kleene algebra

Kleene's theorem

Kleene algebra

From DFAs to regular expressions

2/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starConcatenation We writeL1:L2for theconcatenation of languages L1andL2, dened by: L

1:L2=fxyjx2L1;y2L2g

For example, ifL1=faaagandL2=fb;cgthenL1:L2is the

languagefaaab;aaacg. Later we will prove the following closure property.If L

1and L2are regular languages then so is L1:L2.3/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starKleene star We writeLfor theKleene sta rof the language L, dened by: L =fg [L[L:L[L:L:L[::: For example, ifL3=faaa;bgthenL3contains strings likeaaaaaa, bbbbb,baaaaaabbaaa, etc. More precisely,L3contains all strings overfa;bgin which the letteraalways appears in sequences of length some multiple of 3 Later we will prove the following closure property.If L is a regular language then so is L .4/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starExercise

Consider the language over the alphabetfa;b;cg

L=fxjxstarts withaand ends withcg

Which of the following strings are valid for the languageL:L?1abcabc

2acacac

3abcbcac

4abcbacbc

Answer:

1, 2,3a revalid, bu t4 isn't. (T osplit the string into t wo

L-strings, we'd needcfollowed bya.)5/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starExercise

Consider the language over the alphabetfa;b;cg

L=fxjxstarts withaand ends withcg

Which of the following strings are valid for the languageL:L?1abcabc

2acacac

3abcbcac

4abcbacbc

Answer:

1, 2,3a revalid, bu t4 isn't. (T osplit the string into t wo

L-strings, we'd needcfollowed bya.)5/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starAnother exercise Consider the (same) language over the alphabetfa;b;cg

L=fxjxstarts withaand ends withcg

Which of the following strings are valid for the languageL?1

2acaca

3abcbc

4acacacacac

Answer:

1, 3,4a revalid, bu tnot 2. (In this pa rticularcase, it so

happens thatL=L+fg, but this won't be true in general.)6/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starAnother exercise Consider the (same) language over the alphabetfa;b;cg

L=fxjxstarts withaand ends withcg

Which of the following strings are valid for the languageL?1

2acaca

3abcbc

4acacacacac

Answer:

1, 3,4a revalid, bu tnot 2. (In this pa rticularcase, it so

happens thatL=L+fg, but this won't be true in general.)6/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs

Closure under concatenation and Kleene starNFAs with-transitionsWe can vary the denition of NFA by also allowing transitions

labelled with the special symbol(nota symbol in ). The automaton may (but doesn't have to) perform a spontaneous -transition at any time, without reading an input symbol. This is quite convenient: for instance, we can turn any NFA into an -NFA with justone sta rtstate and one accepting state :ee e e ee. . . . . . . . . . . . . . .. . . . .(Add-transitions from new start state to each state inS, and from each state inFto new accepting state.) 7/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starEquivalence to ordinary NFAs Allowing-transitions is just a convenience: it doesn't fundamentally change the power of NFAs. IfN= (Q;;S;F) is an-NFA, we can convertNto an ordinary NFA with the same associated language, by simply `expanding' andSto allow for silent-transitions. To achieve this, perform the following steps onN.For every pair of transitionsqa!q0(wherea2) and q

0!q00, add a new transitionqa!q00.For every transitionq!q0, whereqis a start state, makeq0

a start state too. Repeat the two steps above until no further new transitions or new start states can be added. Finally, remove all-transitions from the-NFA resulting from the above process. This produces the desired NFA. 8/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starClosure under concatenation We use-NFAs to show, as promised, that regular languages are closed under the concatenation op eration: L

1:L2=fxyjx2L1;y2L2g

IfL1;L2are any regular languages, choose-NFAsN1;N2that dene them. As noted earlier, we can pickN1andN2to have just one start state and one accepting state. Now hook upN1andN2like this:N1 N2eClearly, this NFA corresponds to the languageL1:L2. 9/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraOperations on languages -NFAs Closure under concatenation and Kleene starClosure under Kleene star Similarly, we can now show that regular languages are closed under the

Klee nesta r

op eration: L =fg [L[L:L[L:L:L[::: For supposeLis represented by an-NFANwith one start state and one accepting state. Consider the following-NFA: Ne e

Clearly, this-NFA corresponds to the languageL.

10/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraRegular expressions From regular expressions to regular languagesRegular expressions We've been looking at ways of specifying regular languages via machines (often presented as pictures ). But it's very useful for applications to have more textual w aysof dening languages. A regula rexp ression is a written mathematical exp ressionthat denes a language over a given alphabet .Thebasic regula rexp ressionsa re ;a(fora2)From these, more complicated regular expressions can be built up by (repeatedly) applying the two binary operations +; : and the unary operation . Example: (a:b+)+a We use brackets to indicate precedence. In the absence of brackets, binds more tightly than:, which itself binds more tightly than +.

Soa+b:ameansa+ (b:(a))

Also the dot is often omitted:abmeansa:b11/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraRegular expressions From regular expressions to regular languagesHow do regular expressions dene languages?

A regular expression is itself just a

written exp ression . However, every regular expressionover can be seen asdening an actual languageL()in the following way.L(;) =;,L() =fg,L(a) =fag.L(+) =L()[ L()L(:) =L():L()L() =L() Example:a+badenes the languagefa;b;ba;baa;baaa;:::g.

The languages dened by;;;aare obviouslyregula r.

What's more, we've seen that regular languages are closed under union, concatenation and Kleene star.

This means

every regula rexp ressiondenes a regula rlanguage (Formal proof by induction on the size of the regular expression.) 12/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraRegular expressions From regular expressions to regular languagesExercises

Consider (again) the language

fx2 f0;1gjxcontains an even number of 0'sg Which of the following regular expressions dene the above language?1(1

0101)2(1

010)131

(010)14(1 + 01

0)Answer:2 and 4 dene the required language. 1 do esn't:e.g. 11

doesn't match the expression. 3 doesn't: e.g. 00100 doesn't match the expression. 13/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraRegular expressions From regular expressions to regular languagesExercises

Consider (again) the language

fx2 f0;1gjxcontains an even number of 0'sg Which of the following regular expressions dene the above language?1(1

0101)2(1

010)131

(010)14(1 + 01

0)Answer:2 and 4 dene the required language. 1 do esn't:e.g. 11

doesn't match the expression. 3 doesn't: e.g. 00100 doesn't match the expression. 13/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraKleene's theorem

Kleene algebra

From DFAs to regular expressionsKleene's theorem

We've seen that every regular expression denes a regular language.

Remarkably, the converse is also true:

every regula rlanguage can be dened by a regular expression The equivalence between regular languages and expressions is: Kleene's theoremDFAs and regular expressions give rise to exactly the same class of languages (the regular languages).(For proof, see Kozen, Lecture 9.) As we've already seen, NFAs (with or without-transitions) also give rise to this class of languages. So the evidence is mounting that the class of regular languages is mathematically a very natural and well-behaved one. 14/21

More closure properties of regular languages

Regular expressions

Kleene's theorem and Kleene algebraKleene's theorem

Kleene algebra

From DFAs to regular expressionsKleene algebra

Regular expressions give a

textual w ayof sp ecifyingregula r languages. This is useful e.g. for communicating regular languages to a computer. Another benet: regular expressions can be manipulated using algebraic laws (

Kleene algebra

). For example:

Often these can be used to

simplify regula rexp ressionsdo wntoquotesdbs_dbs17.pdfusesText_23

[PDF] kleene star regular expressions

[PDF] kleene's theorem

[PDF] klingon alphabet

[PDF] klingon dictionary

[PDF] klingon in google translate

[PDF] klingon tr

[PDF] klingon translator audio

[PDF] klm 10k

[PDF] klm airlines annual report 2018

[PDF] klm annual financial report

[PDF] klm cheap flights

[PDF] klm construction services group llc

[PDF] klm credit rating

[PDF] klm hubs

[PDF] klm japan