오토마타·형식언어

문자열과 언어

알파벳 Σ는 기호의 집합이고 Σ는 모든 유한 문자열의 집합입니다. 언어 L은 Σ의 부분집합입니다. 빈 문자열 ε는 길이 0이고, 문자 “0”은 길이 1입니다. 입력이 없다는 것과 숫자 0이라는 기호를 읽는 것은 다릅니다.

이 단원은 Σ={0,1}인 결정적 유한 오토마타 DFA를 사용합니다. DFA는 유한 상태 집합 Q, 알파벳 Σ, 전이 함수 δ:Q×Σ→Q, 초기 상태 q₀, 수용 상태 집합 F로 지정합니다. 각 상태·기호 쌍에 다음 상태가 정확히 하나 있어야 합니다.

상태는 필요한 기억만 남긴다

첫 언어는 1의 개수가 짝수인 모든 문자열입니다. 전체 문자열을 저장할 필요 없이 지금까지의 개수가 짝수인지 홀수인지만 기억하면 됩니다. q₀는 짝수, q₁은 홀수입니다. 기호 0은 상태를 유지하고 1은 두 상태를 바꿉니다. 초기 상태와 수용 상태는 모두 q₀입니다.

입력 101을 읽으면 q₀→q₁→q₁→q₀입니다. 마지막 상태가 수용 상태이므로 수용합니다. 중간에 수용 상태를 방문했다는 것만으로 전체 문자열이 수용되는 것은 아닙니다. 입력을 모두 읽은 뒤 판정합니다.

문자열 전체에 대한 전이

한 기호 전이를 문자열로 확장합니다.

수용 조건은 δ*(q₀,w)∈F입니다. 입력 길이에 대한 귀납법으로 짝수 오토마타의 상태가 읽은 접두사의 1 개수 홀짝과 일치함을 증명할 수 있습니다. 초기 ε는 짝수이고, 0은 홀짝을 유지하며 1은 바꿉니다. 이 불변식이 임의 길이에 대한 정확성 근거입니다. 화면의 길이 8 이하 실험만이 근거는 아닙니다.

01로 끝나는 언어

두 번째 오토마타는 접미사 01의 일치 정보를 기억합니다. q₀는 유용한 접미사가 없음, q₁은 마지막 기호가 0, q₂는 마지막 두 기호가 01인 상태입니다. q₂만 수용 상태입니다.

어느 상태에서든 0을 읽으면 q₁로 갑니다. q₁에서 1을 읽으면 q₂, 다른 상태에서 1을 읽으면 q₀입니다. q₂에서 0은 q₁, 1은 q₀입니다. 예를 들어 010은 q₁에서 끝나 거부되고 0101은 q₂에서 끝나 수용됩니다. 이전에 한 번 01이 나왔다는 조건이 아니라 끝이 01이라는 조건입니다.

실습의 정수 입력을 문자열로 읽기

입력 정수 w의 하위 N비트를 길이 N에 맞게 앞에 0을 채워 표시합니다. w=5,N=3이면 101, w=1,N=3이면 001입니다. N=0이면 w 값과 관계없이 ε입니다. 높은 비트는 이 실습의 문자열에 포함되지 않습니다. 실제 소비한 기호는 표와 식에 명시됩니다.

이중 원은 수용 상태, 주황 테두리는 마지막 상태입니다. 화살표의 0과 1은 확률이나 비용이 아니라 소비하는 기호입니다. 아래 표는 시작 상태와 각 기호 뒤의 상태를 나열합니다.

단어 개수와 확률을 구분하기

짝수 언어의 길이 N≥1인 단어 수는 2^(N−1)입니다. 마지막 비트를 뒤집으면 짝수와 홀수 단어가 일대일 대응하므로 절반입니다. N=0에는 ε 하나가 수용됩니다.

01 언어에서는 N≥2일 때 마지막 두 기호가 고정되고 앞 N−2개는 자유이므로 2^(N−2)개입니다. N<2이면 0개입니다. 이 수를 확률로 바꾸려면 입력 단어의 분포가 필요합니다.

DFA가 인식하는 언어를 정규언어라 합니다. 무제한 중첩 괄호처럼 입력 길이와 함께 기억이 계속 필요한 언어에는 DFA만으로 충분하지 않을 수 있습니다. 유한 예시에서 잘 동작하는 기계를 모든 형식언어의 인식기로 일반화하지 마세요.

AI 연결과 확인 문제

구조화 출력의 일부 형식 제약, 토큰 필터, 프로토콜 상태 검사는 유한 상태로 다룰 수 있습니다. 그러나 토큰화와 문자화는 다른 알파벳이며, DFA가 문법적 형식을 보장해도 사실성이나 의미 정확성을 보장하지는 않습니다.

1. ε는 짝수 언어에서 수용되나요? 그렇습니다. 1의 수가 0입니다.
2. 길이 4의 01 언어 단어 수는? 4개입니다.
3. 입력 011은 01 언어에서 수용되나요? 아니요. 최종 q₀입니다.

추가 읽기: MIT Theory of Computation. 두 작은 기계와 불변식은 직접 구성한 예제입니다.