CSC 240 LECTURE 10
LANGUAGE THEORY
Let ∑ denote a finite alphabet i.e. set of letters.
Recall that ∑* denotes the set of all (finite length) strings over ∑.
If ∑ = {a,b}, then ∑* = { λ, a, b, aa, ab, ba, bb, aaa, …},
where λ is the empty string of length 0. It is sometimes denoted by 𝜀.
A language over ∑ is a subset of ∑* i.e. it is a set of strings over ∑.
Concatenation
if x and y are strings then x・y (or xy)
is the string consisting of all the letters in x followed by all the letters in y.
If x = aab and y = ba then x・y = aabba and y・x = baaab x・λ = λ・x = x, so λ is an identity
If L and L’ are languages then
L・L’ = L L’ = { x・y | x ∈ L and y ∈ L’ }
example
If L = {a,bb} and L’ ={λ, c}
then L・L’ = {ac,bbc,a,bb} ≠ {ca,cbb,a,bb} = L’・L
L0 = {λ} ≠ λ
L1 = L
Li+1 = Li・L = L・Li
L* = U {Li | i ≥ 0}
L+ = U {Li | i ≥ 1}
so L* = L+ U {λ}
L* = L+ if and only if λ ∈ L
x is a prefix of y if there exists a string x’ such that x・x’ = y. x is a suffix of y if there exists a string x’ such that x’・x = y.
They are proper if x’ ≠ λ.
x is a substring of y if there exist strings x’ and x” such that x’・x・x” = y.
It is proper if x’ ≠ λ or x” ≠ λ.
Other operations on languages
Let L, L’ be a language over ∑.
union: L ∪ L’ = { x | (x ∈ L) OR (x ∈ L’)} intersection: L ∩ L’ = { x | (x ∈ L) AND (x ∈ L’)} difference: L – L’ = { x | (x ∈ L) AND (x ∉ L’)} complementation: L = ∑* – L = { x ∈ ∑* | x ∉ L}
Regular Expressions
a concise way of describing some languages
Let ∑ be a finite alphabet.
Let R be the following inductively defined set of strings: φ, λ ∈ R
Σ⊆R
If r,r’ ∈ R, then (r+r’) ∈ R, (r・r’) ∈ R , and r* ∈ R R is called the set of regular expressions over Σ.
A generalized regular expression allows complementation, intersection, difference, and +.
The language denoted by a regular expression r is L(r), where L: R → { L | L ⊆ ∑*} is defined inductively, as follows: L(φ) = φ
L(λ) = { λ }
L(a) = { a } for each a ∈ Σ
L( (r+r’) ) = L(r) ∪ L(r’) for r,r’∈ R
L( (r・r’) ) = L(r)・L(r’) for r,r’∈ R
L( r* ) = (L(r))* for r ∈ R
Similarly for generalized regular expressions. L( (r ∩ r’) ) = L(r) ∩ L(r’)
L( (r-r’) ) = L(r) – L(r’) L(r ̄) = Σ* – L(r)
L( r+ ) = (L(r))+
Note that r ̄ is a shorthand for Σ* – r
so φ is a shorthand for ∑*
Note that brackets can be removed when there is no ambiguity
For example, r1・r2・r3
A language L is regular if and only if L = L( r ) for some r ∈ R. Two regular expressions r and r’ are equivalent, r ≡ r’,
if they denote the same language, i.e. L(r) = L(r’).
Examples:
strings over {a,b,c} that start with ab
ab(abc)* X abc is not in L(ab(abc)*) ={ab, ababc, ababcabc,…} ab・{a,b,c}* X
a・b ・(a+b+c)*
L(a+b+c) = {a,b,c} = {a} ∪ {b} ∪ {c}
strings over {0,1} with even parity, i.e. with an even number of 1’s (0*10*1)*0*
first and last symbols are different over the alphabet {0,1} 0(0+1)*1 + 1(0+1)*0
first and last symbols are different over the alphabet {0,1,2}
(0+1+2)* – (0 (0+1+2)* 0 + 1 (0+1+2)* 1 + 2 (0+1+2)* 2) generalized regular expression, not a regular expression 0(0 + 1 + 2)*1 + 0(0 + 1 + 2)*2 + 1(0 + 1 + 2)*0 + 1(0 + 1 + 2)*2 + 2(0 + 1 + 2)*1 + 2(0 + 1 + 2)*0 √
0(0+1+2)*(1+2) + 1(0+1+2)*(0+2) + 2(0+1+2)*(0+1) Let L = {0i1n | i+n is odd}
((00)* + 1(11)*) + (0(00)* + (11)*) = (00)* + 1(11)* + 0(00)* + (11)* x (00)*(0+1)(11)* √
r = (00)*0(11)* + (00)*1(11)* Prove L = L(r).
To do so, prove L(r) ⊆ L and L ⊆ L(r).
Let x ∈ L.
Then x = 0i1n for some i,n ∈ N such that i+n is odd.
There are 2 cases:
1. i = 2a+1 is odd and n = 2b is even
Then x = (00)a0(11)b ∈ L((00)*0(11)*) ⊆ L(r),
because (00)a ∈ L((00)*), so (00)a0 ∈ L((00)*0), and (11)b ∈ L((11)*)
2. i = 2a is even and n = 2b + 1 is odd
Then x = (00)a(11)b1 ∈ L((00)*(11)*1) ⊆ L(r).
Thus L ⊆ L(r).
Let x ∈ L(r) = L((00)*0(11)*) U L((00)*(11)*1)
Then either x ∈ L((00)*0(11)*) or x ∈ L((00)*(11)*1)
either x = (00)a0(11)b or x = (00)a(11)b1 for some a,b ∈ N.
In the first case x = 0i1n, where i = 2a+1 and n = 2b so i+n is odd.
In the second case x = 0i1n, where i = 2a and n = 2b+1, so i+n is odd. In both cases, x ∈ L.
Thus L(r) ⊆ L. FINITE AUTOMATA
A (deterministic) finite (state) automaton (DFA or DFSA) is another way of describing a language. It uses a very simple model of a machine.
Example 1:
A
It has a finite set of states Q = {q0,q1,q2,q3}.
q0 is the initial state denoted by an arrow pointing into it
D
O Fr
Go
81 Uo
o
I
I I
B
q1,q2 are final states, denoted by a double circle
a set of final states, F = {q1, q2}
∑ = {0,1} finite input alphabet (set of letters), labels that can occur on edges Each directed edge represents a transition from a state to a state.
The label on the edge says what letter causes the transition.
The transitions can be described by a transition function δ:Q x ∑ → Q δ(q0,0) = q2
δ(q0,1) = q1
δ(q1,0) = q1
δ(q1,1) = q1 δ(q2,0) = q2 δ(q2,1) = q3 δ(q3,0) = q2 δ(q3,1) = q3
Formally, a finite automaton is a 5-tuple M = (Q,∑,δ,q0,F), , where Q is a finite set of states,
F ⊆ Q is the set of final states
q0 ∈ Q is the initial state
∑ is a finite alphabet
δ:Q x ∑ → Q is the transition function
Given an input string a1 a2 ・・・ a_n ∈ ∑*,
the finite automaton operates as follows:
-it starts in the initial state
-it reads the input string from left to right, 1 letter at a time,
and changes state according to the transition function
(following the edge labelled by the letter)
-when all the letters have been read, a deterministic finite automaton accepts the string if it is in a final state, i.e. a state in F
rejects the string if it is in a state in Q-F
examples
0110, 100 accepted 0101 is rejected
D
O Fr
Go
81 Uo
If M is a DFA, then the language accepted by M is defined to be L(M) = {x ∈ ∑* | x accepts M}
For the example,
L(A) = { x ∈ {0,1}* | x begins and ends with 0 or x begins with 1}
define the extended transition function δ*:Q x ∑*→ Q by δ*(q,λ) = q
and for all letters a ∈ ∑ and all strings x ∈ ∑*
δ*(q,xa) = δ(δ*(q,x),a)
or, equivalently, δ*(q,ax) = δ*(δ(q,a),x)
L(M) = { x ∈ ∑* | δ*(q0,x) ∈ F}
To prove that L(A) = {x ∈ {0,1}* | x begins and ends with 0 or x begins with 1}, associate a set of strings Li with each state qi such that
L1 ∪ L2 = { x ∈ {0,1}* | x begins and ends with 0 or x begins with 1}.
Then prove by structural induction or by induction on the length of x that
∀ i ∈ {0,1,2,3}. (Li = { x ∈ ∑* | δ*(q0,x) = qi}). L0 = {λ}
L1 = { x ∈ {0,1}* | x begins with 1} = L(1(0+1)*)
L2 = { x ∈ {0,1}* | x begins and ends with 0} = L(0(0+1)*0 + 0) L3 = { x ∈ {0,1}* | x begins with 0 and ends with 1} = L(0(0+1)*1)
A
o
I
I I
B
Example 2
Give a deterministic finite automaton that accepts the language L ( (0+1)*1(0+1) ) = { x in {0,1}* | the second last letter of x is 1}.
7 states:
{λ}
L0 = {0}
L1 = {1}
L00 = {x∈ {0,1}* | x ends in 00} = L((0+1)*00)
L01 = {x∈ {0,1}* | x ends in 01} = L((0+1)*01) L10 = {x∈ {0,1}* | x ends in 10} = L((0+1)*10) L11 = {x∈ {0,1}* | x ends in 11} = L((0+1)*11)
a
4 states:
L’00 = {x∈ {0,1}* | x ends in 00} ∪ {λ,0} L’01 = {x∈ {0,1}* | x ends in 01} ∪ {1} L10 = {x∈ {0,1}* | x ends in 10}
L11 = {x∈ {0,1}* | x ends in 11}
q
to a
O go 0 Goo l 78
UO 7
I
9J 0691
O goh O
The set of states Q of a finite automaton can be thought of as an object with different fields.
For example, Q = S x L, where L stores the last letter read and S stores the second last letter read.
Nondeterministic Finite Automata (NFA, NFSA)
Like a deterministic finite automaton, a nondeterministic finite (state) automaton is a 5-tuple M=(Q,∑,δ,q0, F), but δ:Q x ∑ → 𝒫(Q)
the range of δ is 𝒫(Q) = { Q’ | Q’ ⊆ Q} instead of Q
-allows moves to different states or no states on a given letter
-models choice, for example a robot walking through a maze define the extended transition function
δ*:Q x ∑* → 𝒫(Q) by
δ*(q,λ) = {q}
and for all letters a and all strings x δ*(q,xa) = U {δ(q’,a) | q’ ∈ δ*(q,x)} or, equivalently,
δ*(q,ax) = U {δ*(q’,x) | q’ ∈ δ(q,a)}
A string x is accepted by a finite automaton if there is a path from the start state to an accept state labelled by x.
How is L(M) defined for a nondeterministic finite automaton M? L(M) = { x ∈ ∑* | δ*(q0,x) ∩ F ≠ φ}
gio U
I
I
9,91 O
M accepts the string x if there is a sequence of lucky guesses it can make to bring it from the start state q0 to a final state.
a nondeterministic finite automaton that accepts the language L( (0+1)*1(0+1) ) = { x ∈ {0,1}* | the second last letter of x is 1}
1. The deterministic finite automaton we talked about earlier can be viewed as a nondeterministic finite automaton.
Observation Every deterministic finite automaton can be viewed as a nondeterministic finite automaton by changing its transition function from δ(q,a) = q’ to δ(q,a) = {q’}
for all q ∈ Q and all a ∈ ∑.
2. 3 states
p0: initial state with self loops on 0,1, and edge to p1 on 1 p1: edge to p2 on 0,1
p2: final state, no outedges
I Pcg
OI 0010
1010 are both accepted
I P
Note: it can be much easier to construct a nondeterministic finite automaton than a deterministic finite automaton for some languages.
Are there some languages that can be accepted by nondeterministic finite automata, but not by deterministic finite automata?
0
7 Pz
Theorem For every NFA M = (Q,∑,δ, q0,F),
there is a DFA M’ = (Q’,∑,δ’, q’0,F’)
that accepts the same language i.e. L(M) = L(M’).
Proof (subset construction):
Use generalization:
Let M = (Q,∑,δ, q0,F) be an arbitrary NFA.
The idea is to construct a DFA M’ that keeps track of the states that M could be in as it reads the input string.
Let M’ = (Q’,∑,𝛾,q’0,F’) be defined as follows: Q’ = 𝒫(Q)
q’0 = {q0}
𝛾(S,a) = U{δ(q,a) | q ∈ S} for all S ∈ 𝒫(Q) and a ∈ ∑
F’ = {S ∈ 𝒫(Q) | S ∩ F ≠ φ}. L(M) = L(M’).
For all w ∈ ∑*, let P(w) = “𝛾*({q0},w) = δ*(q0,w)” In other words, (q ∈ 𝛾*({q0},w)) IFF (q ∈ δ*(q0,w)).
Base case: w = λ.
By definition of extended transition function for a DFA, 𝛾*({q0},λ) = {q0}.
By definition of extended transition function for an NFA, δ*(q0,λ) = {q0}. Thus P(λ) is true.
Constructor case: w = xa, where x ∈ ∑* and a ∈ ∑. Assume P(x) is true, so 𝛾*({q0},x) = δ*(q0,x).
By definition of extended transition function for a DFA, 𝛾*({q0},w) = 𝛾(𝛾*({q0},x),a)
= U{δ(q,a) | q ∈ 𝛾*({q0},x) } by construction
= U{δ(q,a) | q ∈ δ*(q0,x) } by substitution
= δ*(q0,w) by definition of extended transition function for an NFA. Thus P(w) is true.
By structural induction, ∀ w ∈ ∑*. P(w).
w ∈ L(M’) if and only if 𝛾*({q0},w) ∈ F’ by definition
since L(M’) = { x ∈ ∑* | 𝛾*({q0},x) ∈ F’}
if and only if 𝛾*({q0},w) ∩ F ≠ φ by construction
since F’ = {S ∈ 𝒫(Q) | S ∩ F ≠ φ}
if and only if δ*(q0,w) ∩ F ≠ φ by substitution since 𝛾*({q0},w) = δ*(q0,w)
if and only if w ∈ L(M) by definition
since L(M) = { x ∈ ∑* | δ*(q0,x) ∩ F ≠ φ}.
Thus L(M’) = L(M).