[Automata] Language Expression to Regular Expression Examples

Language Expression to Regular Expression Examples

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Expression

Algorithm을 증명하는 과정에서 표현 방법을 Language expression으로 나타낼 것인지 Regular expression으로 나타낼 건지에 차이가 있다.

이번 포스트에서는 대표적으로 많이 사용하는 LE와 RE의 차이를 예제를 통해서 살펴보도록 하겠다.

Language Expression	Regular Expression
{ }	∅
{a}	a AND a ∈ Σ
a o b	(|ab|)
a U b	(|a ⋓ b|)
a*	a*

---

# Expression Examples

위의 표를 참고하여 Expression example에 적용해보면 아래와 같다.

Regular expression에서 Language expression으로 전환하고 decomosing 하는 예제이다.

# Example
(|a(|a⋓b|)*|)

L(a) = {a}, L(b) = {b}.

L((|a⋓b|)) is L(a) U L(b) = {a,b}.

L((|a⋓b|)*) is {a, b}*

L((|a(|a⋓b|)*|)) is {a} o {a, b}*

Tree structure로 나타내면 아래와 같은 트리 구조가 나온다.

Fig01.

---