오토마타와 형식언어: 유한 오토마타 (Finite Automata) (5)

김영채 (Kevin)·2020년 4월 19일
0
post-thumbnail

유한 오토마타 마지막 게시글은 아니게 됐다. 아직 다룰 것이 조금 남아서 몇 개만 더 적어보려고 한다.

아래 필기 내용부터 공유하고자 한다.

여기서는 중요한 몇 가지만 짚고 넘어가고자 한다.

위 NFA를 보면 중요한게, 각 상태들 (qo,q1,q2)에서는 보이지는 않지만 람다를 입력받아 스스로의 상태에 남을 수 있다는 것이다. 즉, 따로 표시만 안 했을 뿐이지 qo에서 람다를 받으면 q0으로 갈 수 있고, q1에서 람다를 받으면 q1에 남을 수도 있다.

또, q2에서 람다를 받아 q0 으로 가는 특별한 walk를 따로 표시하지 않는 이상 람다를 받아 다른 state로 가는 것은 불가능하다.

또한, NFA에서 중요한 개념이 하나 더 있다. 바로 λa, aλ, λλa, λλaλλ 모두 같은 입력이 될 수도 있다는 것이다.

위 필기를 보면서 생각해보자. q1에서 a를 받으면 얼핏 보기에는 아무 곳도 못 갈 것처럼 보인다. 그러나 실은 λ를 받으면 q0,q1,q2 모두 갈 수 있다.

q1에서 q0을 가려면 λλaλλ를 받으면 되고, q2를 가려면 λλaλ를 받으면 된다. q1을 가려면 λλa를 받거나 자기 혼자 람다를 받아 돌면 된다.

이처럼 NFA에서는 람다의 역할이 매우 중요한다. 람다가 어떻게 정의되어 있느냐에 따라 전이 함수의 결과값이 완전히 바뀔 수가 있기 때문이다.

profile
맛있는 iOS 프로그래밍

0개의 댓글