Languages and Finite Automata

Languages Costas Busch - LSU 1 Language: a set of strings String: a sequence of symbols from some alphabet Example: Strings: cat, dog, house Language: {cat, dog, house} Alphabet: a, b, c, , z Costas Busch - LSU 2 Languages are used to describe computation problems: PRIMES {2,3,5,7,11,13,17, }

EVEN {0,2,4,6, } Alphabet: {0,1,2, ,9} Costas Busch - LSU 3 Computation is translated to set membership Example computation problem: Is number x prime? Equivalent set membership problem: x PRIMES {2,3,5,7,11,13,17,}?

Costas Busch - LSU 4 Alphabets and Strings An alphabet is a set of symbols Example Alphabet: a, b A string is a sequence of symbols from the alphabet a ab Example Strings abba aaabbbaabab Costas Busch - LSU

String variables u ab v bbbaaa w abba 5 Decimal numbers alphabet 102345 {0,1,2, ,9} 567463386 Binary numbers alphabet 100010001 {0,1}

101101111 Costas Busch - LSU 6 Unary numbers alphabet 1 11 Decimal number:1 2 Unary number: Costas Busch - LSU {1}

111 1111 11111 3 4 5 7 String Operations abba bbbaaa w a1a2 an v b1b2 bm Concatenation wv a1a2 anb1b2 bm Costas Busch - LSU

abbabbbaaa 8 w a1a2 an ababaaabbb Reverse R w an a2a1 bbbaaababa Costas Busch - LSU 9 String Length

w a1a2 an Length: w n Examples: abba 4 aa 2 a 1 Costas Busch - LSU 10 Length of Concatenation uv u v Example: u aab, u 3 v abaab, v 5

uv aababaab 8 uv u v 3 5 8 Costas Busch - LSU 11 Empty String A string with no letters is denoted: or Acts as a neutral element Observations: 0 w w w abba abba abba abba Costas Busch - LSU 12 Substring

Substring of string: a subsequence of consecutive characters String Substring abbab abbab abbab abbab ab abba b bbab Costas Busch - LSU 13

Prefix and Suffix string abbab Prefixes Suffixes a ab abb abba abbab abbab bbab bab ab w uv prefix suffix

b Costas Busch - LSU 14 Exponent Operation n w ww w n Example: Definition: 2 abba abbaabba

0 w abba 0 Costas Busch - LSU 15 * The * Operation : the set of all possible strings from alphabet

a, b * , a, b, aa, ab, ba, bb, aaa, aab, Costas Busch - LSU 16 The + Operation : the set of all possible strings from alphabet except a, b * , a, b, aa, ab, ba, bb, aaa, aab, *

a, b, aa, ab, ba, bb, aaa, aab, Costas Busch - LSU 17 Languages A language over alphabet is any subset of * Example: a, b *

, a, b, aa, ab, ba, bb, aaa, Languages: {} a, aa, aab { , abba, baba, aa, ab, aaaaaa} Costas Busch - LSU 18 More Language Examples Alphabet {a, b} An infinite language L ab aabb

aaaaabbbbb n n {a b : n 0} bbabb L L Costas Busch - LSU abb L 19 Prime numbers Numbers divisible by 1 and itself Alphabet

{0,1,2, ,9} Language: * PRIMES {x : x and x is prime} PRIMES {2,3,5,7,11,13,17,} Costas Busch - LSU 20 Even and odd numbers Alphabet {0,1,2, ,9} Languages: * EVEN {x : x and x is even} EVEN {0,2,4,6, }

* ODD {x : x and x is odd} ODD {1,3,5,7, } Costas Busch - LSU 21 Addition Alphabet: (of unary numbers) {1,, } Language: n m k

ADDITION {x y z : x 1 , y 1 , z 1 , n m k , n 1, m 1} 11 111 11111 ADDITION 111 111 111 ADDITION ADDITION {1 1 11,1 11 111,11 1 111,11 11 1111 , ...} Costas Busch - LSU 22 Squares Alphabet: (of unary numbers) {1, # } Language: n

m 2 SQUARES {x#y : x 1 ,y 1 , m n } 11#1111 SQUARES 111#1111 SQUARES SQUARES {1#1,11#1111 ,111#111111111 , ...} Costas Busch - LSU 23 Two special languages Language with empty string Empty language { } or

{ } Size of a language (number of elements): | {} |0 | |1 | a, aa, ab |3 | { , aa, bb, abba, baba} |5 Costas Busch - LSU 24 Note that: Sets { } { } Set size { } 0

Set size { } 1 String length 0 Costas Busch - LSU 25 Operations on Languages The usual set operations: a, ab, aaaa bb, ab {a, ab, bb, aaaa} union a, ab, aaaa bb, ab {ab} intersection a, ab, aaaa bb, ab a, aaaa difference Complement:

* L L a, ba , b, aa, ab, bb, aaa, Costas Busch - LSU 26 Reverse Definition: R R L {w : w L} Examples: ab, aab, baba R

ba, baa, abab n n L {a b : n 0} R n n L {b a : n 0} Costas Busch - LSU 27 Concatenation Definition: L1L2 xy : x L1, y L2 Example: a, ab, ba b, aa

ab, aaa, abb, abaa, bab, baaa Costas Busch - LSU 28 Another Operation Definition: n L LL L n 3 a, b a, b a, b a, b aaa, aab, aba, abb, baa, bab, bba, bbb Special case: 0

L a, bba, aaa Costas Busch - LSU 0 29 Example n n L {a b : n 0} 2 n n m m L {a b a b : n, m 0} 2

aabbaaabbb L Costas Busch - LSU 30 Star-Closure (Kleene *) All strings that can be constructed fromL Definition: * 0 1 2 L L L L Example:

, a, bb, a, bb * aa , abb , bba , bbbb , aaa, aabb, abba, abbbb, Costas Busch - LSU

0 L 1 L 2 L 3 L 31 Positive Closure Definition: 1

2 3 L L L L * 0 Note that: L L L 1 a, bb, L 2

a, bb aa, abb, bba, bbbb, L aaa, aabb, abba, abbbb, L3 Costas Busch - LSU 32

Recently Viewed Presentations

• Being an effective Physics TA. 5 September 2018. CJ Woodford. Deepak Chandan. A couple notes: - please interrupt and ask questions throughout our talks! - this talk will be online: don't worry about writing anything down
• Collectors who have rigorously applied the Necessity and TEEP tests and collection arrangements are based on well-evidenced, documented and justified decision-making Medium compliance, medium intervention: Collectors who send co-mingled collections to a MRF which is producing poor quality recyclates •...
• Web Time Entry procedures. What is Web Time entry? This is a Datatel process for submitting payroll and leave hours. This method will replace Lotus Notes and allow departmental payroll coordinators to submit hours worked and hours absent (vacation, sick,...
• David possesses over 20 years of experience as a corporate lawyer and President/CEO in the nutritional industry, as well as serving as a member of several boards for nutrition research organizations. David has served as CEO of Metabolife and as...
• Introduction to Python LinuxWorld - New York City - January 2002 Guido van Rossum Director of PythonLabs at Zope Corporation [email protected] [email protected]
• 11. ss {IkvXh. PohnXw. k`bnepw. kaql¯nepw. kotdm. ae_mÀ. k`bpsS. hnizmk] cnioe \ ] mTmhen. c£bpsS]mXbnÂþ11
• Case law on informed consent: Sidaway. v. Bethlem. Royal Hospital [1985] AC 871(what the reasonable doctor would disclose) Moyes. v. Lothian Health Board. 1990 SLT 444 (ditto for Scotland) Chester v. Afshar [2004] 4 All ER 587 (what the reasonable...
• His heavily armour train pull into the station just after 8am , after a 65-hour , 4,500km journey from Pyongyang via mainland China . Just a they do during Kim Il-sung ' s visit 55 year ago , a dozen...