CT :: Ch1. Regular Language

1. Finite Automata

 1) Definition of FA

 Define FA M = (Q, ∑, δ, q0, F)

 Q : a finite set of states

 ∑ : a finite set of alphabets

 δ : transition function ( Q x ∑ -> Q )

 q0: start state

 F : the set of accept states

2. Language and Machine

 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

  <-> L(M) = A

  <-> M recognizes A

  <-> A = { w | M accepts w}

 2) Acceptability

 M accepts w

  <-> a sequence of states r0, r1 … r(n) is 

      Q exists with 3 conditions:

     1) r0 = q0

     2) Delta( r(i), w(i+1) ) = r(i+1)

     3) r(n) ∈ F

  ※ How can we prove the fact that Automata A equals Automata B?

   : prove that L(A) = L(B) like this.

     …

3. Regular Language

 1) Definition of RL

  Language A is a regular language if some FA recognizes it

  (Exam) Design FA that recognizes given regular language. 

 2) Operations:

  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 }

        = A₀ ∪ A₁ ∪ A₂ ∪ …

 3) Closed under the union operator?

  <-> if A, B are RLs then so is A ∪ B

  (proof)

  Let A, B be RLs,

     L(M1) = A, L(M2) = B,

     M1 = (Q1, ∑, δ1, q1, F1),

     M2 = (Q2, ∑, δ2, q2, F2)

 Define M’ = (Q, ∑, δ, q0, F).

 Q = { (r1, r2) | r1 ∈ Q1 and r2 ∈ Q2 }

 δ = δ( (r1, r2) , a ) = ( δ(r1, a) , δ(r2, a) )

 q0= (q1, q2)

 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 …

4. Nondeterminism

 1) Characteristics

 δ: 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

 2) Definition of NFA

 NFA N = (Q, ∑, δ, q0, F)

 Q : a finite set of states

 ∑ : a finite set of alphabets

 δ : transition function ( Q x ∑ε -> P(Q) )

 q0: start state

 F : the set of accept states

 3) Equivalence of NFAs and DFAs

 (proof by induction)

 Let  A be RL

  NFA N = (Q, ∑, δ, q0, F)

  DFA M = (Q’, ∑, δ’, q0’, F’)

 - Basis

   : 만약 N이 ε을 accept할 때, 
     q0로부터 ε으로 transition가능한 state집합을 E(q0)라고 하면,

     q0’ = E(q0)이고 for r ∈ q0’, r ∈ F, thus q0’ ∈ F’,

     so that, M accept ε.

     또한 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.

 - Steps:

   : 만약 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한다.

 - Conclusion:

   : By Basis and Steps, L(N)-> L(M),

     and L(M)->L(N)

     ∴ NFA = DFA (동치)

 4) Relation of Regular Language and NFA

 : A is a RL if and only if there exist NFA recognizes A

 (proof)

 NFA can be converted into an equivalent DFA

 Therefore, there exist DFA recognizes A

5. Closure under the Regular Operation (3)

 1) Union    ∪

 If L1, L2 be RLs, (L1 ∪ L2) is a RL

 Let N1, N2 are NFAs such that L1 = L(N1), L2 = L(N2)

 (proof)

 <->  there exist NFA N recognizes (L1 ∪ L2)

 Let N1 = (Q1, ∑, δ1, q1, F1)

     N2 = (Q2, ∑, δ2, q2, F2)

 Construct N = (Q, ∑, δ, q0, F) to recognize (L1 ∪ L2)

 Q = Q1 U Q2 U {q0}

 δ = δ1(q, a)  if q ∈ Q1

     δ2(q, a)  if q ∈ Q2

     {q1, q2}  if q = q0 and a ∈ ε

     ∅         if q = q0 and a ∉ ε

 F = F1 U F2

 1) Concatenation ∘ 

 If L1, L2 be RLs, (L1 ∘ L2) is a RL

 Let N1, N2 are NFAs such that L1 = L(N1), L2 = L(N2)

 (proof)

 <->  there exist NFA N recognizes (L1 ∘ L2)

 Let N1 = (Q1, ∑, δ1, q1, F1)

     N2 = (Q2, ∑, δ2, q2, F2)

 Construct N = (Q, ∑, δ, q1, F2) to recognize (L1 ∘ L2)

 Q = Q1 U Q2

 δ = δ1(q, a)         if q ∈ Q1, q ∉ F1

     δ1(q, a)         if q ∈ F1, a ∉ ε

     δ1(q, a) U {q2}  if q ∈ F1, a ∈ ε

     δ2(q, a)         if q ∈ Q2

 1) Kleene Star *

 If L1 be a RL, L1* is a RL

 Let N are NFAs such that L1 = L(N)

 (proof)

 <->  there exist NFA N recognizes L1*

 Let N1 = (Q1, ∑, δ1, q1, F1)

 Construct N = (Q, ∑, δ, q0, F1) to recognize L1*

 Q = Q1 U {q0}

 δ = δ1(q, a)         if q ∈ Q1, q ∉ F1

     δ1(q, a)         if q ∈ F1, a ∉ ε

     δ1(q, a) U {q1}  if q ∈ F1, a ∈ ε

     {q1}             if q = q0, a ∈ ε

     ∅                if q = q0, a ∉ ε

6. Regular Expression

 1) Definition of RE

    : R is a regular expression if R is

  (1) symbol a for some a in the alphabet ∑,

  (2) ε,

  (3) ∅,

  (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

    (proof: two direction)

  (1) If A is described by a RE, then A is a RL

     (proof by case-by-case)

     if R = a, ➝◯─a➝◎

     if R = ε, ➝◎

     if R = ∅, ➝◯

     if R = R1 U R2

     if R = R1 ∘ R2

     if R = R1*

  (2) If A is a RL, there exists a RE describes it

     (concept: converting from DFA to GNFA, from GNFA to RE)

7. Non-Regular Language

   *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)