Automata

용어 정리

알파벳(alphabet)

alphabet T 는 symbol 들의 유한 집합

• 심벌 a,b,c 에 대한 알파벳 T={a,b,c}
• 심벌 가,나,다,라 에 대한 알파벳 T={가,나,다,라}

스트링(string)

알파벳 T 에 대한 스트링은 T 에 속하는 문자를 하나이상 모은 것

• 알파벳 T={a,b,c} 일 때 , 스트링은 a,aaa,abc,aabbc,....

스트링의 크기(length)

스트링을 이루는 심벌의 수

알파벳 T={a,b,c} 일 때 ,

• 스트링 a 의 크기는 1 , 기호로 |a|=1
• 스트링 aabc 의 크기는 4 , 기호로 |aabc|=4

스트링의 연결(concatenation)

스트링의 접속

스트링 U=ab, 스트링 V=def 라면 ,

• U · V=abdef 이고
• V · U=defab 임.

스트링의 연결에서는 교환 법칙이 성립하지 않음

공 스트링(empty string)

길이가 0 인 스트링(기호로 ε)

| ε | = 0

+ , ·

+ 는 or 를 , · 는 연결을 의미

aⁿ, a⁰,a^*,a⁺

• aⁿ 는 심벌 a 를 n 개 나열한 것(aa...a)
• a⁰ 는 공 스트링 ε
• a⁺ 는 심벌 a 를 하나 이상(a + aa + aaa + aaaa ...)
• a^* 는 심벌 a 를 0 개 이상 나열한 것(ε + a + aa + aaa+ aaaa ...)

(보기) 만들수 있는 스트링은?

1. a+b 는 a 혹은 b
2. (a+b)² = (a+b)(a+b) a+b 에서 a 혹은 b 를 만들수 있으므로 aa,ab,ba,bb
3. (a+b)c^*
4. ab⁺c^*
5. (a+b)⁺c^*d⁺
6. a²(c+d)²e⁺f^*