유한 오토마타를 다루는 마지막 게시글이 될 것 같다. 유한 오토마타와 더불어 "정규 언어(Regular Language)에 대해서도 좀 다루었다. 아무래도 문제 풀이 위주의 게시글이 될 것 같다.
첫 번째 문제다.
{0,1}에 대한 문자열들 가운데 부문자열 001을 포함하는 string을 제외한 모든 문자열을 승인하는 dfa를 구성하여라.
001을 제외한 모든 문자열을 승인하라니, 처음에는 많이 헷갈렸다.
우선 답안은 아래와 같다.
이제껏 q0, q1, q2 이런식으로 각 상태들을 나타냈지만, 이번에는 001이라는 부문자열이 들어오는지 안 들어오는지 확실히 기억하기 쉽게 각 상태들에 대해 label을 붙여줬다.
시작은 λ이며, 0이 처음에 input이 되면 상태가 0임을 쉽게 알 수 있게 q1에다가 "0"이라는 라벨을 붙여줬다.
각 상태들에 라벨(Label)을 붙여줌으로써 더 직관적으로 dfa 구성이 가능하다.
이 문제에서 주의해야 할 것은 substring 001이라는 것이다. 즉, 처음에 001이 들어온다고 그것만 막으면 되는 것이 아니라, 긴 string 중간에도 001이라는 부문자열이 들어오는 것을 막아야 한다는 것이다.
살짝 돌려서 생각하면, 001을 제외한 모든 state는 승인 상태에 남게 된다는 것을 알 수 있다.
그리고, 001이 입력되는지 확인하기 위해, 하나 하나의 input symbol뿐만 아니라, 그 직전에 2개의 00이 선행되었는지를 검사해야 한다. 그래야 다음에 1이 들어왔을 때 부문자열 001이 됐구나라는 것을 인식해 해당 string을 거절할 수 있게 된다.
또한, 거부 상태는 반드시 trap state이어야 한다.
이제, 위와 같이 dfa를 구성했을 때 string acceptance test를 거쳐보도록 하자.
string 이 100100일 때 => 거절(reject) // 001 포함
string 이 1010100일 때 => 승인(accept) // 001 미포함
정규 언어 (Regular Language)
다음은 정규 언어이다.
정규 언어란?
=> 언어 L에 대하여, L=L(M)을 만족하는 dfa M이 존재하고 오직 그럴 때에만 L을 정규 언어라 부른다.
예제를 보자.
다음 언어 L이 정규 언어임을 보여라
우선, input alphabet은 a,b, 또는 람다이다. {a,b}* (star-closure)가 포함되어 있기 때문이다.
그리고, awa 를 보면, 시작과 끝이 a이기만 하면 어떠한 string 이든지 accept한다는 것을 쉽게 알 수 있다.
여기서, 위 L이 정규 언어임을 보이기 위해서는 그 언어에 대한 dfa를 찾으면 된다.
awa를 보면 알겠지만, a가 처음에 읽혀지고, 또 다른 a가 읽혀질 때마다 dfa를 승인 상태에 놓이게 하면 될 것 같다는 생각이 든다. a로 시작하고 끝나야 하기 때문에, b가 input으로 들어오면 승인 상태에서 벗어나게끔 하면 된다.
구성된 dfa는 아래와 같다.
(오른쪽 아래의 빨간색 화살표 표시는 무시 바란다.)
이렇게 주어진 L에 대해 dfa가 구성되어서, 이 언어가 정규 언어임을 알 수 있다.
