[Automata] Examples of Tree Structure and Regular Expression

Examples of Tree Structure and Regular Expression

---

포스트 난이도: HOO_Junior

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

---

 

# Examples of Tree Structure and Regular Expression

예를 들어, 아래와 같은 Regular expression이 있다고 가정해보자.

(|a(|a U b|)^*|)

해당 RE를 Tree structure로 나타내면 아래와 같다.

Fig01. Tree structure

해당 RE를 language represented로 나타낸다고 한다면 Tree structure를 참고하면 된다.

Language represented도 Tree structure처럼 하나하나 나눠서 설명해서 표현해주면 되기 때문이다.

처음 보기에는 막막해 보일 수는 있지만 사실 어려운 게 아니니 차근차근 살펴보면 쉽게 이해할 수 있다.

• L(a) = {a}, L(b) = {b}.
• L(|a U b|) is L(a) U L(b) = {a, b}.
• L((|a U b|)^*) is {a, b}^*.
• L(|a(|a U b|)^*)) is {a} o {a, b}^*.

RE를 Language represented로 나타내기 위해서는 하나하나 나눠서 설명해줘야 한다.

만약에 RE가 복잡해서 바로 확인이 불가능하다면, 위와 같이 Tree structure를 그려주고 나서 Language represented로 나타내 주는 것도 좋은 방법이다.

---