[계산이론](8)[regular expression -> regular language]

모든 regular expression은 regular language를 recognize할 수 있는가?
모든 regular language는 regular expression으로 표현될 수 있는가?
-> 참 (즉, r.e와 DFA, NFA는 모두 표현력이 같다.)

 

Regular expression -> Regular language 증명

즉, regular expression이 NFA로 표현됨을 증명

 

기본 규칙에 대한 NFA

r.e의 기본 요소들은 NFA로 충분히 나타낼 수 있다.

• {a}, $단, \ a \in \sum$
  N = (${q_1, q_2}$, $\sum$, $\delta$, $q_1$, ${q_2}$)
  단, δ(q1, a) = q2, (단, δ(r, b) = ∅ {r≠q1, a≠b}
  

  

• ε
  N = (${q_1}$, $\sum$, $\delta$, $q_1$, ${q_1}$)
  단, δ(r, b) = ∅ {모든 r, b에 대해}
  

  

• ∅
  N = (${q_1}$, $\sum$, $\delta$, $q_1$, ∅)
  단, δ(r, b) = ∅ {모든 r, b에 대해}
  

  

-> 따라서 기본 요소들은 모두 NFA로 표현 가능
즉, regular language다!

 

귀납적 규칙에 대한 NFA

• $(R_1 \cup R_2), \ 단, \ R_1, \ R_2$가 regular expression
• $(R_1R_2), \ 단, \ R_1, \ R_2$가 regular expression
• $(R_1^*), \ 단, \ R_1$가 regular expression

이것들 모두 앞에서 regular language에 대해 닫혀있다 증명했다.
따라서 기본 요소로 연산하면 이것 또한 regular language다.

 

 

예) (ab∪a)* 의 NFA를 그리시오
     규칙에 맞춰 그리자!! (같은 language더라도 기계적으로 규칙에 맞춰...)

     a, b의 NFA

 

     ab의 NFA

 

 

     (ab∪a)의 NFA

 

     (ab∪a)*의 NFA