Languages
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
Alphabets and Strings
We will use small alphabets:
Strings
a
ab
abba
baba
aaabbbaabab
a, b
u ab
v bbbaaa
w abba
3
String Operations
w a1a2 an
abba
bbbaaa
v b1b2 bm
Concatenation
wv a1a2 anb1b2 bm
abbabbbaaa
4
w a1a2 an
ababaaabbb
Reverse
R
w an a2 a1
bbbaaababa
5
String Length
w a1a2 an
Length:
Examples:
w n
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 111
1111
4
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
Induction basis:
v 1
From definition of length:
uv u 1 u v
9
Inductive hypothesis:
uv u v
vfor
1,2, , n
Inductive step: we will prove
for
uv u v
v n 1
10
Inductive Step
Write
v wa,
w n, a 1
where
From definition of length: uv
uwa uw 1
wa w 1
From inductive hypothesis:
Thus:
uw u w
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
abbab
abbab
abbab
ab
abba
b
bbab
13
Prefix and Suffix
abbab
Prefixes
Suffixes
a
ab
abb
abba
abbab
abbab
bbab
bab
ab
b
w uv
prefix
suffix
14
Another Operation
n
w ww
w
n
Example:
Definition:
abba abbaabba
2
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
ab
aabb
aaaaabbbbb
n n
L {a b : n 0}
abb L
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:
Examples:
L {w : w L}
ab, aab, baba ba, baa, abab
R
n n
L {a b : n 0}
R
n n
L {b a : n 0}
21
Concatenation
Definition:
Example:
L1L2 xy : x L1, y L2
a, ab, ba b, aa
ab, aaa, abb, abaa, bab, baaa
22
Another Operation
Definition:
L LL L
n
a, b a, b a, b a, b
aaa, aab, aba, abb, baa, bab, bba, bbb
3
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 : n, m 0}
2
aabbaaabbb L
24
Star-Closure (Kleene *)
Definition:
L* L L L
Example:
a, bb,
a, bb *
aa
,
abb
,
bba
,
bbbb
,
aaa, aabb, abba, abbbb,
25
Positive Closure
Definition:
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
a
b
q1 b q2 b q3 a
initial
state
state
transition
a, b
q4
final
state
accept
30
Initial Configuration
a b b a
Input String
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
31
Reading the Input
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
32
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
33
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
34
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
35
a b b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
Output: accept
36
Rejection
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
37
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
38
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
39
a b a
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
40
a b a
a, b
b
q0 a
Output:
q5 reject
a, b
a
a
b
q1 b q2 b q3 a
q4
41
Another Example
a a b
a, b
q0
q1
a, b
q2
42
a a b
a, b
q0
q1
a, b
q2
43
a a b
a, b
q0
q1
a, b
q2
44
a a b
a, b
q0
q1
a, b
q2
45
a a b
a
q0
Output: accept
q1
a, b
a, b
q2
46
Rejection
b a b
a, b
q0
q1
a, b
q2
47
b a b
a, b
q0
q1
a, b
q2
48
b a b
a, b
q0
q1
a, b
q2
49
b a b
a, b
q0
q1
a, b
q2
50
b a b
a, b
q0
q1
a, b
q2
Output: reject
51
Formalities
Deterministic Finite Accepter (DFA)
M Q, , , q0 , F
Q : set of states
: input alphabet
q0
: transition function
: set of final states
: initial state
52
Input Aplhabet
a, b
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
53
Set of States Q
Q q0 , q1, q2 , q3 , q4 , q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
54
Initial State q0
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
55
Set of Final States F
F q4
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
56
Transition Function
:Q Q
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
57
q0 , a q1
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
58
q0 , b q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
59
q2 , b q3
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
60
q0
q1
q2
q3
q4
q5
a
q1
q5
q2
q4
q5
q5
Transition Function
b
q5
q2
q3
q5
q5
q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
61
Extended Transition Function *
* : Q * Q
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
62
* q0 , ab q2
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
63
* q0 , abba q4
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
64
* q0 , abbbaa q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
65
Observation: There is a walk from q0 to
with label abbbaa
q1
* q0 , abbbaa q5
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
66
Recursive Definition
* q, q
* q, wa ( * (q, w), a )
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
67
* q0 , ab
* (q0 , a ), b
* q0 , , a , b
q0 , a , b
q1 , b
q2
a, b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
68
Languages Accepted by DFAs
Take DFA
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
a
b
q1 b q2 b q3 a
a, b
q4
accept
70
Another Example
L M , ab, abba
M
a, b
q5
q0 a
accept
a
b
q1 b q2 b q3 a
accept
a, b
q4
accept
71
Formally
For a DFA
M Q, , , q0 , F
Language accepted by
L M w * : * q0 , w F
alphabet
transition
function
initial
state
final
states
72
Observation
Language accepted by M :
L M w * : * q0 , w F
Language rejected by M :
L M w * : * q0 , w F
73
More Examples
L M {a b : n 0}
n
a, b
q0
q1
accept
a, b
q2
trap state
74
L M = { all substrings with prefix ab }
a, b
q0
q1
q3
q2
accept
a, b
75
L M = { all strings without
substring 001 }
0
0,1
00
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
is regular:
L awa : w a, b *
a
b
q0
b
q2
q3
a
b
q4
a, b
78
