Define FA M = (Q, ∑, δ, q0, F)
Q : a finite set of states
∑ : a finite set of alphabets
δ : transition function ( Q x ∑ -> Q )
F : the set of accept states
1) Relation of Language and Machine
Let A is the set of all strings that machine M accepts,
<-> A is the language of machine M
<-> A = { w | M accepts w}
<-> a sequence of states r0, r1 … r(n) is
Q exists with 3 conditions:
2) Delta( r(i), w(i+1) ) = r(i+1)
※ How can we prove the fact that Automata A equals Automata B?
: prove that L(A) = L(B) like this.
Language A is a regular language if some FA recognizes it
(Exam) Design FA that recognizes given regular language.
Let A, B be regular languages,
(1) Union: A ∪ B = { x | x ∈ A or x ∈ B }
(2) Concatenation: A ∘ B = { xy | x ∈ A and y ∈ B }
(3) Star: A* = { x₁x₂ … x(k) | k ≥ 0, x(i) ∈ A }
3) Closed under the union operator?
<-> if A, B are RLs then so is A ∪ B
M1 = (Q1, ∑, δ1, q1, F1),
Define M’ = (Q, ∑, δ, q0, F).
Q = { (r1, r2) | r1 ∈ Q1 and r2 ∈ Q2 }
δ = δ( (r1, r2) , a ) = ( δ(r1, a) , δ(r2, a) )
F = (F1 x Q2) ∪ (Q1 x F2) = { (r1, r2) | r1 ∈ F1 or r2 ∈ F2 }
Since FA M’ which recognizes A ∪ B is defined,
so by RL definition, A ∪ B is RL.
4) Closed under the concatenation operator?
<-> if A, B are RLs then so is A ∘ B.
(Problem) Where should we break its input into 2 pieces?
We don’t know …
δ: a state may have 0, 1, more arrows for each alphabet symbol
∑: a state may have arrows labeled with the alphabet or ε
Acceptability: if anyone of transition paths acceptable,
NFA accepts the input
Q : a finite set of states
∑ : a finite set of alphabets
δ : transition function ( Q x ∑ε -> P(Q) )
F : the set of accept states
3) Equivalence of NFAs and DFAs
DFA M = (Q’, ∑, δ’, q0’, F’)
: 만약 N이 ε을 accept할 때,
q0로부터 ε으로 transition가능한 state집합을 E(q0)라고 하면,
q0’ = E(q0)이고 for r ∈ q0’, r ∈ F, thus q0’ ∈ F’,
또한 N이 symbol x를 accept할 때,
q0로부터 x로 transition가능한 state집합을 E(q1)라고 하면,
q1’ = E(q1)이고 q1’의 r ∈ q1’, r ∈ F, thus q1’ ∈ F’
so that, M accepts every string w whose length is 1.
: 만약 N이 w ∈ A(n)를 accept한다면,
M이 w ∈ A(n)를 accept한다고 가정하자.
그리고 w가 n번째 symbol일때,
N이 도착한 state를 q(n), M이 도착한 state를 r(n)이라 하자.
이 때, 만약 NFA N이 |v| = n+1인 v를 accept한다면,
NFA N이 q(n)까지 오는 동안 n개에 대해 transition하고,
q(n)에서 마지막 symbol 1개에 대한 transition을 accept한다.
그리고 가정에서 n개 이하의 길이에 대해
N이 accept하면 M도 accept하므로,
DFA M도 r(n)까지 오는 동안 n개에 대해 transition하고,
r(n)에서 마지막 symbol 1개에 대한 transition을 accept한다.
즉, NFA N이 w ∈ A(n)를 accept할 때, M이 w ∈ A(n)를 accept하고,
NFA N이 |v| = n+1인 v를 accept할 때, DFA M도 v를 accept한다.
그러므로 만약 N이 w’ ∈ A(n+1)를 accept한다면,
M도 w’ ∈ A(n+1)를 accept한다.
: By Basis and Steps, L(N)-> L(M),
4) Relation of Regular Language and NFA
: A is a RL if and only if there exist NFA recognizes A
NFA can be converted into an equivalent DFA
Therefore, there exist DFA recognizes A
5. Closure under the Regular Operation (3)
If L1, L2 be RLs, (L1 ∪ L2) is a RL
Let N1, N2 are NFAs such that L1 = L(N1), L2 = L(N2)
<-> there exist NFA N recognizes (L1 ∪ L2)
Let N1 = (Q1, ∑, δ1, q1, F1)
Construct N = (Q, ∑, δ, q0, F) to recognize (L1 ∪ L2)
{q1, q2} if q = q0 and a ∈ ε
If L1, L2 be RLs, (L1 ∘ L2) is a RL
Let N1, N2 are NFAs such that L1 = L(N1), L2 = L(N2)
<-> there exist NFA N recognizes (L1 ∘ L2)
Let N1 = (Q1, ∑, δ1, q1, F1)
Construct N = (Q, ∑, δ, q1, F2) to recognize (L1 ∘ L2)
δ = δ1(q, a) if q ∈ Q1, q ∉ F1
δ1(q, a) if q ∈ F1, a ∉ ε
δ1(q, a) U {q2} if q ∈ F1, a ∈ ε
If L1 be a RL, L1* is a RL
Let N are NFAs such that L1 = L(N)
<-> there exist NFA N recognizes L1*
Let N1 = (Q1, ∑, δ1, q1, F1)
Construct N = (Q, ∑, δ, q0, F1) to recognize L1*
δ = δ1(q, a) if q ∈ Q1, q ∉ F1
δ1(q, a) if q ∈ F1, a ∉ ε
δ1(q, a) U {q1} if q ∈ F1, a ∈ ε
: R is a regular expression if R is
(1) symbol a for some a in the alphabet ∑,
(4) (R1 U R2), where R1 and R2 are REs,
(5) (R1 ∘ R2), where R1 and R2 are REs,
(6) R1*, where R1 is a RE.
2) Equivalence between RE with FA
A is a RL if and only if there exists a RE describes it
(1) If A is described by a RE, then A is a RL
(2) If A is a RL, there exists a RE describes it
(concept: converting from DFA to GNFA, from GNFA to RE)
*Pumping Lemma: Technique for proving non-regularity
If A is a RL,
s is any string in A, |s| >= p,
which may be divided into three pieces, s = xyz,
satisfying the following 3 conditions:
1. for each i >= 0, x(y^i)z ∈ A,
2. |y| > 0,
3. |xy| <= p.
(proof concept)
There exist a FA accepting finite every input string.
About infinite length,
Let total number of states be p.
If length of string s is p, necessary amount is p+1.
Thus, by pigeonhole principle,
at least one state is duplicated.
About duplicated 2 state,
Let the state be q1, q2.
We can think that string of q0~q1 be x,
string of q1~q2 be y,
string of q2~q(p+1) be z.
and since q1 = q2,
1. for i >= 0, x(y^i)z ∈ A
2. |y| = q1~q2 > 0 (at least 1, because between 2 states)
3. |xy| = q0~q2 <= p (maximum p, because max-length is p)
