[Automata] NFA Examples

NFA Examples

---

포스트 난이도: HOO_Junior

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

---

 

# Regular Expression

아래와 같은 예제가 있다고 가정해보자.

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

우선 Regular expression을 간단하게 분석해본다.

a와 b라는 변수가 존재하고 o, *, U 등이 해당 RE에 있는 걸 알 수 있다.

다음으로 Regular expression을 NFA로 만들어주기 위해서는 우선적으로 Tree structure를 통해 이해하는 것이 편하다.

Tree strucutre로 Regular expression을 표현하면 한눈에 단계별 확인이 가능하기 때문에 보다 더 쉽게 NFA를 정확히 만들어낼 수 있다.

 

---

# Tree Structure

Fig01.

위의 그림은 예제 RE를 LE 방식의 Tree strucuture로 나타낸 그림이다.

Tree 구조를 통해 RE에 대한 구조적 이해가 훨씬 쉬워지기에 NFA를 그리는 데 있어서 도움이 된다.

우선 Tree 구조를 살펴보았을 때 a가 먼저 나와야 하며 a와 b가 합쳐지는데(or) 반복되어 나올 수도 있다는 걸 *이 나타내고 있다.

이제부터는 단계별 하나씩 NFA를 그려보면 된다.

---

# NFA

NFA를 그릴 때에는 하위 단계부터 시작해주는 것이 좋다.

제일 하위 단계인 a와 b에 대해서 그림을 그려보면 아래와 같다.

Fig02. Na

Fig03. Nb

a와 b에 대한 부분을 그렸으면 다음 단계를 적용해주면 된다.

a와 b는 U이기 때문에 이 부분을 만들어주면 된다.

Fig04. aub

aUb NFA를 그려주면 위와 같이 만들어줄 수 있다.

NFA이기 때문에 empty를 사용하여 만들어줄 수 있다.

또한 aUb이기 때문에 a나 b로 가도 최종 결과인 q1에 도달할 수 있다.

aub가 완성되었다면 다음 상위 단계인 (aub)* 부분을 추가하여 그려주면 된다.

Fig05. (aub)*

이 부분에서 유의할 점은 (aub)가 반복될 여지가 있기 때문에 q1 aub에서 q0 aub로 돌아가는 empty 화살표를 넣어주어야 한다.

또한 마찬가지로 (aub)*라는 의미는 (aub)가 발생하지 않을 수도 있기 때문에 empty인 상태로 q0에서 q1으로 종료될 수 있도록 하는 부분도 추가해줘야 한다.

(aub)* 부분까지 완료되었다면 다음 최종 단계인 ao(aub)* 부분을 만들어준다.

Fig06. ao(aub)*

---