Theory of computation (7)

본 내용은 KOCW 한양대학교 “오토마타 및 계산이론” 강좌 9, 10강을 보며 정리한 내용입니다.

regular grammers
1. right linear grammer / left linear grammer

right linear grammer 는 nonterminal symbol이 오른쪽에 있을때 입니다.

$$A \to x B$$ $$A \to x$$

non terminal 인 $B$ 가 오른쪽에 있으므로 right linear grammer 입니다.

right linear grammer의 예로는

$$S \to abS \mid a$$

반대로 nonterminal symbol 이 왼쪽에 있으면 left linear grammer 라고 부릅니다.

$$A \to B x$$ $$A \to x$$

left linear grammer의 예로는

$$S \to S_1 ab$$ $$S_1 \to S_1 ab \mid S_2$$ $$S_2 \to a$$

left / right linear grammer 는 regular grammer 라고 합니다.

left / right linear grammer 둘다 아닌 것을 linear grammer 라고 부릅니다.

여기서 linear grammer 는 regular grammer 라고 부르지는 않습니다.

linear grammer의 예는

$$S \to A$$ $$A \to aB \mid \lambda$$ $$B \to Ab$$

linear grammer로 표현할수 있는 language는 right / left linear grammer로 표현할수 있는 language 보다 더 많습니다.

right linear grammer 가 주어졌을때 regular expression 으로 표현할수 있습니다.

$$S \to abS \mid a$$

위와 같은 right linear grammer 가 있을때 grammer를 만족하는 regular expression을 나타내면 다음과 같습니다.

$$(ab)^* a$$ 2. closure properties of regular languages

$L_1$ , $L_2$ regular language 가 있다고 한다면 다음에서도 regular language 로 닫혀있습니다. (closed)

$1. \text{ } L_1 \cup L_2$

• $L_1$ 는 regular expression 으로 $r_1$ 이라고 하고, $L_2$ 는 regular expression 으로 $r_2$ 라고 한다면 $L_1 \cup L_2$ 는 $r_1 + r_2$ 로 나타낼수 있고 이것도 regular language 이므로 $L_1 \cup L_2$ 도 regular language 라는 것을 알수 있습니다.

$2. \text{ } \overline{L_1}$

• $L_1$ 의 compliment 도 regular language 입니다.

• regular language 는 NFA로 나타낼수 있고, $L_1$ 은 regular language 이므로 NFA로 나타낼수 있습니다. 거기서 final state는 final state가 아니게 해주고, final state 가 아닌 것은 final state로 바꿔 주게 되면 $\overline{L_1}$ 도 regular language 라는 것을 알수 있습니다.

$3. \text{ } L_1 \cap L_2$

• $L_1 \cap L_2 = \overline{\bar{L_1} \cup \bar{L_2}}$ 로 나타낼수 있습니다.

  • 집합 공식 : $A\cap B = (A^c \cup B^c)^c$

• 위의 1번과 2번으로 인해서 $L_1 \cap L_2$ 도 regular language 라는 것을 알수 있습니다.

$4. \text{ } L_1 - L_2$

• $L_1 - L_2 = L_1 \cap \overline{L_2}$ 로 나타낼수 있습니다.

  • 집합 공식 : $A- B = A \cap B^c$
• 위의 2번과 3번에 의해서 $L_1 - L_2$ 도 regular language 라는 것을 알수 있습니다.

$5. \text{ } reversal$

• reversal 은 string들을 뒤집은 것을 애기 합니다.

• regular language 는 NFA 가 항상 존재하고 initial stae와 final state도 1개씩 존재하게 됩니다. 그 상태에서 initial state와 final state만 서로 바꿔주면 reversal 도 regular language 가 됨을 알수 있습니다.

$6. \text{ } homomorphism$

다음과 같이 $\Sigma = \{a, b\}, \Gamma = \{a, b, c\}$

alphabet 은 $\Sigma$에 있는것으로 하고, homomorphism 을 적용한 string은 $\Gamma$ 에서 만들어집니다.

예를 들어보면

$$h(a) = ab$$ $$h(b)=bbc$$

이면

$$h(aba)=abbbcab$$

가 됩니다.

$L = \{aa, aba\}$ 이면 homomorphism 을 적용한 $h(L)$은 다음과 같습니다.

$$h(L)=\{abab, abbbcab\}$$