20160302 Automata and Theory of Computation

language, alphabet, string.

alphabet

alphabet은 기호로 나타낸다.

예를 들어 a부터 z까지의 알파벳을 쓰는 언어는 다음과 같이 나타낼 수 있다.

string

string은 문자를 연결한 것이다.

string의 각 문자를 index로 표현하기

string 는 다음과 같이 index로도 표현할 수 있다.

string concatenation

string 와 string 가 있을 때, 라고 쓰면, 두 string을 붙인 것이다.

string reverse

string length

null string : (lambda)

길이가 0인 string을 라 부른다.

substring

  • 원래 string의 일부 string.
  • prefix : substring이면서 원본 string의 앞부분.
  • suffix : substring이면서 원본 string의 뒷부분.

표현

string의 집합

  • 시그마 스타

null string을 제외한 string의 집합

  • 시그마 플러스

Language

language : 의 부분집합.

예 : 알파벳을 조금씩 다르게 사용하는 많은 언어. 유럽의 여러 나라들.

L Complement(여집합)

L reverse : L의 모든 sentence를 reverse 한 집합

이고 라면,

이 된다.

  • 집합 의 원소의 개수 최대값은 집합 의 원소의 개수 집합 의 원소의 개수이다.
    • 최대값? 중복이 발생할 수 있기 때문.

  • null string, 즉 만 있는 집합은 공집합과 다르다는 점에 주의할 것.

  • 반복의 합집합.

Grammar

  • V : variables
    • 영어로 비유하자면 주어, 동사, 형용사…
  • T : terminal symbols
    • 단어들.
  • S : start variable
    • V 중에서 특별히 시작할 때 사용하는 것들.
  • P : productions
    • 우리가 일반적으로 문법이라 부르는 것. 문법 구조.

다음 예를 보자.

  • V : start variable만 들어 있음.
  • T : a, b 만 들어 있음.
  • S : V가 하나 뿐이므로, .
  • P : Production rule 은 두 가지.
    • 로 바꾸는 것.
    • 로 바꾸는 것.

이를 사용해 sentence를 만들 수 있다.

S에서 시작해 Variable이 없어질 때까지 P를 반복 적용(, derivation)한다.

따라서 다음과 같은 derivation이 가능하다.

다음은 Production을 몇 번 적용하건 간에 에서 가 나올 수 있다는 말.

다음은 Production을 몇 번 적용하건 간에 에서 가 나올 수 있다는 말.

한편 와 같이 Terminal로만 이루어진 것을 sentence라고 부른다.

그리고 와 같이 sentence가 될 수 있는 형태를 sentential form이라 부른다.

Grammar와 Language의 관계 정의

Language : Grammar가 주어지면, Start Variable 에서부터 모든 derivation으로 나올 수 있는 모든 가능한 sentence의 집합.

다음과 같은 Language를 생각해 보자.

이런 랭귀지를 생성하는 그래머는 어떻게 만들 수 있을까?

Production rule을 얼마나 잘 만드는지에 달려 있다.

아래쪽의 두 Production rule을 잘 보면 을 만들 수 있다는 것을 알 수 있다.

그렇다면 만 붙여주면 을 만들 수 있게 되는 것이다.

위의 Production rule로 생성되는 결과는 아래와 같은 특징이 있다.

즉, a 와 b 의 개수가 같은 모든 string을 생성하는 규칙이다.