Automata Theory - University of San Francisco

1 Automata TheoryCS411 2015F-02 Formal LanguagesDavid GallesDepartment of Computer ScienceUniversity of San Francisco02-0:Alphabets & StringsAnalphabet is a finite set of symbols 1= {a, b,.., z} 2= {0, 1}Astringis a finite sequence of symbols from analphabetfire, truck are both strings over {a,.., z}length of a string is the number of symbols in thestring|fire|= 4,|truck|= 502-1:Alphabets & StringsTheempty string is a string of 0 characters| |= 0 is theconcatenationoperatorw1= fire,w2= truckw1 w2= firetruckw2 w1= truckfirew2 w2= trucktruckOften drop the :w1w2= firetruckFor any stringw,w =w02-2:Concatenation & ReversalWe can concatenate a string with itself:w1=ww2=www3=wwwBy definition,w0= Can reverse a string:wRtruckR= kcurt02-3.

2 Formal LanguageAformal language(or justlanguage) is a set ofstringsL1={a, aa, abba, bbba}L2={car, truck, goose}L3={1, 11, 111, 1111, 11111,..}A language can be either finite or infinite02-4:Language ConcatenationWe can concatenate languages as well as stringsL1L2={wv:w L1 v L2}{a, ab}{bb, b} =02-5:Language ConcatenationWe can concatenate languages as well as stringsL1L2={wv:w L1 v L2}{a, ab}{bb, b} = {abb, ab, abbb}{a, ab}{a, ab} =02-6:Language ConcatenationWe can concatenate languages as well as stringsL1L2={wv:w L1 v L2}{a, ab}{bb, b} = {abb, ab, abbb}{a, ab}{a, ab} = {aa, aab, aba, abab}{a, aa}{a, aa} =02-7:Language ConcatenationWe can concatenate languages as well as stringsL1L2={wv.}

3 W L1 v L2}{a, ab}{bb, b} = {abb, ab, abbb}{a, ab}{a, ab} = {aa, aab, aba, abab}{a, aa}{a, aa} = {aa, aaa, aaaa}What can we say about|L1L2|, if we know|L1|=mand|L2|=n?02-8:Language ConcatenationWe can concatenate a language with itself, just likestringsL1=L, L2=LL, L3=LLL, shouldL0be, and why?02-9:Language ConcatenationWe can concatenate a language with itself, just likestringsL1=L, L2=LL, L3=LLL, { }{}is the empty language{ }is the trivial languageKleene Closure (L )L =L0 L1 L2 L3 ..02-10:Regular ExpressionsRegular expressions are a way to describe formallanguagesRegular expressions are defined recursivelyBase case simple regular expressionsRecursive case how to build more complexregular expressions from simple regularexpressions02-11.

4 Regular Expressions is a regular expression, representing { } is a regular expression, representing {} a , a is a regular expression representing {a}ifr1andr2are regular expressions, then(r1r2)is aregular expressionL[(r1r2)] =L[r1] L[r2]ifr1andr2are regular expressions, then(r1+r2)is a regular expressionL[(r1+r2)] =L[r1] L[r2]ifris regular expressions, then(r )is a regularexpressionL[(r )] = (L[r]) 02-12:Regular ExpressionsRegular Expression DefinitionRegular Expression Language L[ ] ={ } L[ ] ={}a L[a] ={a}(r1r2)L[r1r2] =L[r1]L[r2](r1+r2)L[(r1+r2)] =L[r1] L[r2](r )L[(r )]=(L[r]) 02-13:Regular Expressions(((a+b)(b*))a)((a((a+b)*))a)( (a*)(b*))((ab)*)02-14:Regular Expressions(((a+b)(b*))a){aa, ba, aba, bba, abba, bbba, abbba, bbbba.}

5 }((a((a+b)*))a){aa, aaa, aba, aaaa, aaba, abaa, abba,..}((a*)(b*)){ , a, b, aa, ab, bb, aaa, aab, abb, bbb,..}((ab)*){ , ab, abab, ababab, abababab,..}02-15:Regular ExpressionsAll those parenthesis can be confusingDrop them!!(((ab)b)a) becomes abbaWhat about a+bb*a what s the problem?02-16:Regular ExpressionsAll those parenthesis can be confusingDrop them!!(((ab)b)a) becomes abbaWhat about a+bb*a what s the problem?Ambiguous!a+(b(b*))a, (a+b)(b*)a, (a+(bb))*a ?02-17 PrecedenceFrom highest to Lowest:Kleene Closure *ConcatenationAlternation +ab*c+e = (a(b*)c) + e(We will still need parentheses for some regular expres-sions: (a+b)(a+b))02-18:Regular ExpressionsIntuitive Reading of Regular ExpressionsConcatenation == is followed by + == or * == zero or more occurances (a+b)(a+b)(a+b)(a+b)*aab(aa)*02-19:Regul ar ExpressionsAll strings over {a,b} that start with an a02-20:Regular ExpressionsAll strings over {a,b} that start with an aa(a+b)*All strings over {a,b} that are even in length02-21.

6 Regular ExpressionsAll strings over {a,b} that start with an aa(a+b)*All strings over {a,b} that are even in length((a+b)(a+b))*All strings over {0,1} that have an even number of1 :Regular ExpressionsAll strings over {a,b} that start with an aa(a+b)*All strings over {a,b} that are even in length((a+b)(a+b))*All strings over {0,1} that have an even number of1 *(10*10*)*All strings over a, b that start and end with thesame letter02-23:Regular ExpressionsAll strings over {a,b} that start with an aa(a+b)*All strings over {a,b} that are even in length((a+b)(a+b))*All strings over {0,1} that have an even number of1 *(10*10*)*All strings over a, b that start and end with thesame lettera(a+b)*a + b(a+b)*b + a + b02-24:Regular ExpressionsAll strings over {0, 1} with no occurrences of 0002-25:Regular ExpressionsAll strings over {0, 1} with no occurrences of 001*(011*)*(0+1*)All strings over {0, 1} with exactly one occurrenceof 0002-26.

7 Regular ExpressionsAll strings over {0, 1} with no occurrences of 001*(011*)*(0+1*)All strings over {0, 1} with exactly one occurrenceof 001*(011*)*00(11*0)*1*All strings over {0, 1} that contain 10102-27:Regular ExpressionsAll strings over {0, 1} with no occurrences of 001*(011*)*(0+1*)All strings over {0, 1} with exactly one occurrenceof 001*(011*)*00(11*0)*1*All strings over {0, 1} that contain 101(0+1)*101(0+1)*All strings over {0, 1} that do not contain 0102-28:Regular ExpressionsAll strings over {0, 1} with no occurrences of 001*(011*)*(0+1*)All strings over {0, 1} with exactly one occurrenceof 001*(011*)*00(11*0)*1*All strings over {0, 1} that contain 101(0+1)*101(0+1)*All strings over {0, 1} that do not contain 011*0*02-29:Regular ExpressionsAll strings over {/, * , a.}

8 , z } that form valid CcommentsUse quotes to differentiate the * in the inputfrom the regular expression *Use [a-z] to stand for (a + b + c + d +..+ z)02-30:Regular ExpressionsAll strings over {/, * , a,.., z } that form valid CcommentsUse quotes to differentiate the * in the inputfrom the regular expression *Use [a-z] to stand for (a + b + c + d +..+ z)/ * ([a-z]+/)* ( * ( * )*[a-z]([a-z]+/)*)* * ( * )*/This exact problem (finding a regularexpression for C comments) has actually beenused in an industrial :Regular LanguagesA language isregularif it can be described by aregular Languages(LREG) is the set of alllanguages that can be represented by a regularexpressionSet of set of stringsRaises the question: Are there languages that arenot regular?

9 Stay tuned!