```Languages
1
Languages
A language is a set of strings
String: A sequence of letters
Examples: “cat”, “dog”, “house”, …
Defined over an alphabet:
  a , b , c ,  , z 
2
Alphabets and Strings
We will use small alphabets:   a , b 
Strings
a
ab
u  ab
abba
v  bbbaaa
baba
w  abba
aaabbbaaba b
3
String Operations
w  a1 a 2  a n
abba
v  b1b 2  b m
bbbaaa
Concatenation
wv  a1 a 2  a n b1b 2  b m
abbabbbaaa
4
w  a1 a 2  a n
ababaaabbb
Reverse
w
R
 a n  a 2 a1
bbbaaababa
5
String Length
w  a1 a 2  a n
Length:
w n
Examples:
abba  4
aa  2
a 1
6
Recursive Definition of Length
For any letter: a  1
For any string wa :
Example:
wa  w  1
abba  abb  1
 ab  1  1
 a 111
1111
4
7
Length of Concatenation
uv  u  v
Example:
u  aab ,
u 3
v  abaab ,
v 5
uv  aababaab
8
uv  u  v  3  5  8
8
Proof of Concatenation Length
Claim:
uv  u  v
Proof: By induction on the length
v
Induction basis: v  1
From definition of length:
uv  u  1  u  v
9
Inductive hypothesis: uv  u  v
for v  1, 2 ,  , n
Inductive step: we will prove uv  u  v
for v  n  1
10
Inductive Step
Write v  wa ,
where
w  n,
a 1
From definition of length: uv  uwa  uw  1
wa  w  1
From inductive hypothesis: uw  u  w
Thus:
uv  u  w  1  u  wa  u  v
11
Empty String
A string with no letters: 
Observations:
 0
w  w   w
 abba  abba   abba
12
Substring
Substring of string:
a subsequence of consecutive characters
String
Substring
abbab
ab
abbab
abba
abbab
b
abbab
bbab
13
Prefix and Suffix
abbab
Prefixes
Suffixes

abbab
a
bbab
ab
bab
abb
ab
abba
b
abbab

w  uv
prefix
suffix
14
Another Operation
w
n
 ww

w




n
Example:
 abba   abbaabba
2
Definition: w
0

 abba   
0
15
The * Operation
 * : the set of all possible strings from
alphabet 
  a , b 
 *   , a , b , aa , ab , ba , bb , aaa , aab ,  
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 ,  
17
Language
A language is any subset of  *
Example:
  a , b 
 *   , a , b , aa , ab , ba , bb , aaa ,  
Languages:  
a , aa , aab 
{  , abba , baba , aa , ab , aaaaaa } 18
Another Example
An infinite language
n
L  {a b
n
: n  0}

ab
L
abb  L
aabb
aaaaabbbbb
19
Operations on Languages
The usual set operations
a , ab , aaaa   bb , ab   { a , ab , bb , aaaa }
a , ab , aaaa   bb , ab   { ab }
a , ab , aaaa   bb , ab   a , aaaa 
Complement:
L   * L
a , ba    , b , aa , ab , bb , aaa ,  
20
Reverse
Definition:
L
R
 {w
R
: w  L}
Examples: ab , aab , baba  R  ba , baa , abab
n n
L  { a b : n  0}
L
R
n n
 {b a : n  0}
21

Concatenation
Definition:
L1 L 2   xy : x  L1 , y  L 2 
Example: a , ab , ba b , aa 
 ab , aaa , abb , abaa , bab , baaa 
22
Another Operation
Definition:
n
L 
LL
L
n
a , b   a , b a , b a , b  
3
aaa , aab , aba , abb , baa , bab , bba , bbb 
0
Special case: L   
a , bba , aaa 0   
23
More Examples
n n
L  { a b : n  0}
2
n n m m
L  {a b a b
aabbaaabbb
: n , m  0}
L
2
24
Star-Closure (Kleene *)
Definition: L *  L  L  L 
0
1
2
Example:
 ,

 a , bb ,



a , bb *  

aa
,
abb
,
bba
,
bbbb
,


 aaa , aabb , abba , abbbb ,  
25
Positive Closure
Definition:

1
2
L  L  L 
 L *   
 a , bb ,




a , bb    aa , abb , bba , bbbb ,

 aaa , aabb , abba , abbbb ,  


26
Finite Automata
27
Finite Automaton
Input
String
Output
Finite
Automaton
String
28
Finite Accepter
Input
String
Finite
Automaton
Output
“Accept”
or
“Reject”
29
Transition Graph
Abba -Finite Accepter
a,b
q5
b
q0 a
a
q1 b
initial
state
state
a
q2 b
b
q3 a
transition
a,b
q4
final
state
“accept”
30
Initial Configuration
a b b a
Input String
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
31
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
32
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
33
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
34
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
35
a b b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
Output: “accept”
36
Rejection
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
37
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
38
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
39
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
40
a b a
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
Output:
“reject”
a,b
q4
41
Another Example
a
a b
a,b
a
q0
b
q1
a,b
q2
42
a
a b
a,b
a
q0
b
q1
a,b
q2
43
a
a b
a,b
a
q0
b
q1
a,b
q2
44
a
a b
a,b
a
q0
b
q1
a,b
q2
45
a
a b
a
q0
Output: “accept”
b
q1
a,b
a,b
q2
46
Rejection
b
a b
a,b
a
q0
b
q1
a,b
q2
47
b
a b
a,b
a
q0
b
q1
a,b
q2
48
b
a b
a,b
a
q0
b
q1
a,b
q2
49
b
a b
a,b
a
q0
b
q1
a,b
q2
50
b
a b
a,b
a
q0
b
q1
a,b
q2
Output: “reject”
51
Formalities
Deterministic Finite Accepter (DFA)
M  Q ,  ,  , q 0 , F 
Q
: set of states

: input alphabet
 : transition function
q 0 : initial state
F
: set of final states
52
Input Aplhabet 
  a , b 
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
53
Set of States Q
Q  q 0 , q1 , q 2 , q 3 , q 4 , q 5 
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
54
Initial State q 0
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
55
Set of Final States F
F  q 4 
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
56
Transition Function 
 :Q    Q
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
57
  q 0 , a   q1
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
58
 q0 , b   q5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
59
 q 2 , b   q3
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
60
Transition Function 

a
q0
q1
b
q5
q1
q5
q2
q2
q2
q3
q3
q4
q5
q4
q5
q5
q5
q5
q5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
61
Extended Transition Function  *
 * : Q  *  Q
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
62
 *  q 0 , ab   q 2
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
63
 *  q 0 , abba   q 4
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
64
 *  q 0 , abbbaa   q 5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
65
Observation: There is a walk from q 0 to q1
with label abbbaa
 *  q 0 , abbbaa   q 5
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
66
Recursive Definition
 * q ,    q
 *  q , wa    ( * ( q , w ), a )
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
67
 * q 0 , ab  
  * ( q 0 , a ), b  
   * q 0 ,  , a , b  
  q 0 , a , b  
 q 1 , b  
a,b
q2
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
68
Languages Accepted by DFAs
Take DFA M
Definition:
The language L  M  contains
all input strings accepted by M
L  M  = { strings that drive M to a final state}
69
Example
L  M   abba 
M
a,b
q5
b
q0 a
a
q1 b
a
q2 b
b
q3 a
a,b
q4
accept
70
Another Example
L  M    , ab , abba 
M
a,b
q5
b
q0 a
accept
a
q1 b
a
q2 b
accept
b
q3 a
a,b
q4
accept
71
Formally
For a DFA
M  Q ,  ,  , q 0 , F 
Language accepted by M :
L  M   w   * :  *  q 0 , w   F 
alphabet
transition
function
initial
state
final
states
72
Observation
Language accepted by M :
L  M   w   * :  *  q 0 , w   F 
Language rejected by M :
L  M   w   * :  *  q 0 , w   F 
73
More Examples
L  M   { a b : n  0}
n
a,b
a
q0
b
q1
accept
a,b
q2
trap state
74
L  M  = { all substrings with prefix ab }
a,b
q0
a
q1
b
a
q3
b
q2
accept
a,b
75
L  M  = { all strings without
substring 001 }
1
0
0 ,1
1

0
0
00
1
001
0
76
Regular Languages
A language L is regular if there is
a DFA M such that L  L  M 
All regular languages form a language family
77
Example
The language L  awa : w  a , b  *
is regular:
b
a
b
q0
a
q2
q3
a
b
q4
a,b
78
```