• 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)\)을 만족하는 정규 표현이 적어도 하나 존재한다.