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