형식언어와 오토마타.03.02

• CHAPTER 3. REGULAR LANGUAGES AND REGULAR GRAMMARS
  • 3.1 REGULAR EXPRESSIONS
  • 3.2 CONNECTION BETWEEN REGULAR EXPRESSIONS AND REGULAR LANGUAGES
• 챕터 3. 정규 언어와 정규 문법
  • 3.1 정규 표현
  • 3.2 정규 표현과 정규 언어의 관계

The two concepts are essentially the same

• 두 개념은 본질적으로 같다.
• 정규 언어에 대응하는 정규 표현이 반드시 존재한다.
• 정규 표현에 대응하는 정규 언어가 반드시 존재한다.

THEOREM 3.1
Let $r$ be a regular expression. Then there exists some nondeterministic finite accepter that accepts $L(r)$. Consequently, $L(r)$ is a regular language.

• 정규 표현 $r$에 대하여
  • 언어 $L(r)$을 accept하는 nfa가 적어도 하나 존재한다.
    • nfa: nondeterministic finite accepter
  • 그러므로 $L(r)$은 정규 언어이다.

증명은 생략. 책을 읽자.

THEOREM 3.2
Let $L$ be a regular language. Then there exists a regular expression $r$ such that $L = L(r)$.

• 정규 언어 $L$에 대하여,
  • $L = L(r)$을 만족하는 정규 표현이 적어도 하나 존재한다.