방송대 이산수학 14강: 오토마타와 형식 언어

방송대 이산수학 14강: 오토마타와 형식 언어

오토마타, 마르코프 연쇄, 형식 문법은 서로 떨어진 주제처럼 보이지만 모두 ‘현재의 정보에서 다음 상태를 정한다’는 공통 구조를 가집니다. 이 글은 결정적·비결정적 상태 전이를 직접 추적하고, 확률 전이를 행렬곱으로 계산하며, 생성 규칙이 문자열과 언어를 만드는 과정을 연결해 14강의 전체 관계망을 재구성합니다.

입력에서 언어까지 세 표현을 한 지도에 놓는다

오토마톤은 입력을 받아 상태를 바꾸는 추상 기계입니다. 전이가 하나로 정해지면 유한 오토마타처럼 입력 문자열을 인식할 수 있고, 전이에 확률을 붙이면 다음 상태의 분포를 다루는 마르코프 연쇄가 됩니다. 한편 문자열을 받아들이는 관점의 반대편에는 규칙으로 문자열을 만들어 내는 형식 문법이 있습니다.

대상	현재 정보	다음 단계	핵심 질문
유한 오토마타	현재 상태와 입력 기호	다음 상태 하나 또는 상태들의 집합	문자열을 받아들이는가
마르코프 연쇄	현재 상태	확률에 따른 다음 상태	몇 단계 뒤 각 상태에 있을 확률은 얼마인가
형식 문법	현재 문자열과 적용할 생성 규칙	규칙을 적용한 새 문자열	목표 문자열을 생성할 수 있는가
촘스키 계층	생성 규칙의 제한	생성 가능한 언어의 범위	어떤 계산 장치가 그 언어를 인식하는가

튜링 기계는 무한히 이어진다고 가정한 테이프, 테이프의 기호를 읽고 쓰는 헤드, 현재 상태를 저장하는 장치와 유한한 명령표로 설명되는 추상 계산 모형입니다. 강의는 이 모형을 가장 넓은 제0유형 언어와 연결하고, 규칙을 더 제한할수록 선형 한정 오토마톤, 푸시다운 오토마톤, 유한 오토마톤으로 인식 장치가 좁아지는 큰 그림을 제시합니다.

관계의 핵심: 오토마타는 문자열을 ‘인식’하는 쪽에서, 문법은 문자열을 ‘생성’하는 쪽에서 같은 언어를 바라봅니다. 마르코프 연쇄는 상태 전이라는 골격을 공유하되, 전이 결과가 참·거짓이 아니라 확률분포라는 점이 다릅니다.

유한 오토마타는 현재 상태와 입력으로 다음 상태를 만든다

출력을 포함한 일반적인 유한 오토마타는 여섯 요소의 순서쌍 M=(I,O,Q,f,g,σ)로 나타냅니다. I는 입력 알파벳, O는 출력 알파벳, Q는 유한한 상태 집합, f:Q×I→Q는 상태 전이 함수, g:Q×I→O는 출력 함수, σ는 초기 상태입니다. 상태도에서 원은 상태를, 화살표는 전이를 나타내며, 화살표의 ‘입력/출력’ 표시는 해당 입력을 읽을 때 출력하고 이동하는 결과입니다.

강의의 두 상태 기계는 Q={s₀,s₁}, I={0,1}, O={a,b}입니다. s₀에서는 입력 0일 때 s₁로 가고 입력 1일 때 s₀에 남으며, 두 경우 모두 a를 출력합니다. s₁에서는 입력 0일 때 s₁에 남고 입력 1일 때 s₀로 가며, 두 경우 모두 b를 출력합니다.

현재 상태	입력 0: 다음 상태/출력	입력 1: 다음 상태/출력
s0	s1/a	s0/a
s1	s1/b	s0/b

입력 01000110을 한 칸씩 추적한다

1. 초기 상태 s₀에서 0을 읽으면 a를 출력하고 s₁로 갑니다.
2. s₁에서 1을 읽으면 b를 출력하고 s₀로 갑니다.
3. 남은 000110에도 같은 규칙을 반복해 현재 상태를 매번 갱신합니다.
4. 출력을 순서대로 이어 붙이면 ababbbaa가 됩니다.

입력 전체를 한꺼번에 보고 출력 패턴을 짐작하면 상태 변경을 놓치기 쉽습니다. 각 기호마다 ‘현재 상태 확인 → 출력 기록 → 다음 상태로 이동’을 반복하는 표를 그리면 상태도와 전이표가 같은 정보를 표현한다는 사실도 확인할 수 있습니다.

DFA는 한 경로를, NFA는 가능한 경로의 집합을 추적한다

언어 인식에 초점을 맞춘 유한 오토마타는 출력 함수를 빼고 M=(I,Q,f,F,σ)의 다섯 요소로 나타냅니다. F는 최종 상태의 집합입니다. 입력을 모두 소비한 뒤 현재 상태가 F에 속하면 문자열을 받아들이고, 그렇지 않으면 거부합니다.

결정적 유한 오토마타는 다음 상태가 하나다

DFA의 전이 함수는 f:Q×I→Q입니다. 상태와 입력 기호의 쌍마다 다음 상태가 정확히 하나 정해집니다. 강의의 DFA는 s₀가 초기 상태이고 s₂가 최종 상태이며 전이는 다음과 같습니다.

현재 상태	입력 0	입력 1	역할
s0	s1	s0	끝의 연속된 0이 없음
s1	s2	s0	끝에 0이 하나 있음
s2	s2	s0	끝에 0이 둘 이상 있음

따라서 이 기계가 받아들이는 언어는 끝부분에 0이 두 개 이상 연속하는 이진 문자열입니다. 10101은 마지막 기호 1을 읽고 s₀에서 끝나므로 거부하지만, 01100은 마지막 두 0을 거쳐 s₂에서 끝나므로 받아들입니다. 최종 상태를 한 번 지나갔는지가 아니라 입력을 모두 읽은 시점의 상태가 판정 기준입니다.

비결정적 유한 오토마타는 여러 가능성을 함께 유지한다

NFA에서는 f:Q×(I∪{ε})→P(Q)처럼 다음 상태가 없거나 하나 이상일 수 있습니다. ε-전이는 입력 기호를 소비하지 않고 이동합니다. 가능한 경로 가운데 하나라도 입력 전체를 소비하고 최종 상태에 도달하면 문자열을 받아들입니다.

강의의 첫 NFA는 s₀에서 1을 읽어 s₁로 가고, s₁에서 0을 원하는 만큼 읽은 뒤 ε로 s₂로 옮겨 1을 원하는 만큼 읽습니다. 따라서 형태는 10^*1^*이고 10011을 받아들입니다. 또 다른 NFA는 s₀에서 0을 반복하고 ε로 s₁, 다시 ε로 최종 상태 s₂에 간 뒤 1을 반복하므로 {0ⁿ1^m | n,m≥0}을 받아들입니다. 두 번의 ε-이동만으로 최종 상태에 갈 수 있어 빈 문자열도 포함합니다.

오개념 교정: NFA가 입력을 임의로 무시하는 것은 아닙니다. ε-전이에서만 입력을 소비하지 않으며, 최종적으로는 주어진 입력 기호를 모두 순서대로 소비한 경로가 있어야 합니다.

전이에 확률을 붙이면 마르코프 연쇄가 된다

마르코프 연쇄는 이산적인 시점에 상태가 바뀌는 확률 과정으로, 다음 상태의 확률이 현재 상태만으로 결정된다는 마르코프 성질을 가집니다. 과거 상태가 i₀,…,i_n이었다는 모든 정보를 알고 있어도 현재 상태 i_n이 주어지면 다음 상태 j의 조건부확률은 같다는 뜻입니다.

P(X_n+1=j | X₀=i₀,…,X_n=i_n) = P(X_n+1=j | X_n=i_n)

한 단계 전이확률은 p_ij=P(X_n+1=j | X_n=i)로 쓰며, 모든 j에 대한 한 행의 합은 1입니다. 시간이 달라도 같은 p_ij를 사용하면 정상 마르코프 연쇄라 하고, 전이확률들을 행렬로 모은 것을 전이행렬 P라 합니다.

오늘의 날씨	내일 맑음	내일 비	내일 눈	행의 합
맑음	0.6	0.3	0.1	1
비	0.8	0	0.2	1
눈	0.3	0.3	0.4	1

상태도에서는 i에서 j로 향하는 화살표에 p_ij를 표시합니다. 행렬의 i행 j열과 상태도의 i→j 화살표가 같은 전이를 나타내므로, 행과 열의 순서를 먼저 고정해야 방향을 뒤집는 실수를 피할 수 있습니다.

행렬곱은 여러 단계의 모든 중간 경로를 합친다

m단계 뒤 i에서 k로 갈 확률과 이어서 n단계 뒤 k에서 j로 갈 확률을 곱하고, 가능한 모든 중간 상태 k에 대해 더하면 i에서 j까지 m+n단계에 도달할 확률이 됩니다. 이것이 Chapman–Kolmogorov 방정식입니다.

p_ij^(m+n) = Σ_k p_ik^(m)p_kj⁽ⁿ⁾

정상 마르코프 연쇄에서는 n단계 전이행렬이 Pⁿ입니다. 행렬곱의 (i,j) 성분이 바로 모든 중간 상태 k를 거치는 경로의 곱을 합한 값이므로, 경로 나열과 행렬곱은 같은 계산입니다.

두 상태 날씨 예제를 경로로 검산한다

상태 0을 건조, 상태 1을 습윤이라 하고 전이행렬이 P=[[0.826,0.174],[0.600,0.400]]이라고 하겠습니다. 현재 습윤일 때 이틀 뒤 건조일 확률은 중간 날씨 두 경우를 모두 합합니다.

1→0→0: 0.600×0.826,   1→1→0: 0.400×0.600
합계: 0.4956+0.2400=0.7356≈0.736

현재 건조일 때 이틀 뒤 습윤일 확률도 두 경로를 더해야 합니다.

0→0→1: 0.826×0.174,   0→1→1: 0.174×0.400
합계: 0.143724+0.069600=0.213324≈0.213

강의자료 수치 점검: 강의 슬라이드의 식은 두 경로를 적었지만 결과를 0.0696으로 표시해 0→0→1 경로의 값을 누락한 것으로 보입니다. 행렬곱과 경로합으로 다시 계산하면 올바른 값은 0.213324입니다.

초기 분포는 행벡터로 왼쪽에서 곱한다

세 상태의 전이행렬이 P=[[0.1,0.5,0.4],[0.6,0.1,0.3],[0.4,0.5,0.1]]일 때 강의에서 계산한 P²은 [[0.47,0.30,0.23],[0.24,0.46,0.30],[0.38,0.30,0.32]]입니다. 각 상태에 100명씩 있다는 행벡터 [100,100,100]을 왼쪽에서 곱하면 이분 뒤 분포는 [109,106,85]입니다. 합계가 300으로 보존되는지도 함께 확인하면 전치나 덧셈 오류를 빠르게 찾을 수 있습니다.

계산 습관: Pⁿ의 각 행 합이 1인지, 확률이 0과 1 사이인지, 초기 인원 총합이 곱셈 뒤에도 보존되는지를 검사하십시오. 이 세 검산은 행·열 방향과 누락 경로를 잡아냅니다.

알파벳에서 문자열의 집합인 언어를 만든다

알파벳 Σ는 기호들의 유한하고 공집합이 아닌 집합이며, 문자열은 그 기호들을 유한 개 나열한 것입니다. 아무 기호도 없는 빈 문자열은 λ로 표시하고 길이는 0입니다. Σⁿ은 길이가 정확히 n인 문자열의 집합, Σ⁺는 길이가 1 이상인 모든 문자열의 집합, Σ^*는 여기에 λ까지 포함한 집합입니다. 형식 언어는 Σ^*의 임의의 부분집합입니다.

표현	허용 길이	Σ={0,1}일 때 앞부분
Σ0	0	{λ}
Σ2	정확히 2	{00,01,10,11}
Σ+	1 이상	{0,1,00,01,10,11,…}
Σ*	0 이상	{λ,0,1,00,01,10,11,…}

두 언어의 연결은 L₁L₂={xy | x∈L₁, y∈L₂}로 정의합니다. L₁={a,ab}, L₂={c,bc}라면 L₁L₂={ac,abc,abbc}이고 L₂L₁={ca,cab,bca,bcab}입니다. 문자열을 붙이는 순서가 결과를 바꾸므로 일반적으로 언어의 연결은 교환법칙을 만족하지 않습니다.

반면 언어의 합집합과 교집합은 보통의 집합 연산과 같습니다. L^*=L⁰∪L¹∪L²∪…이고 L⁰={λ}이므로 어떤 L이든 L^*에는 λ가 포함됩니다. L⁺=L¹∪L²∪…에는 λ가 자동으로 포함되지 않습니다.

형식 문법은 생성 규칙으로 언어를 정의한다

구구조 문법은 G=(V,T,P,S)의 네 요소로 정의합니다. V는 비단말 기호의 유한집합, T는 단말 기호의 유한집합, P는 생성 규칙의 집합, S∈V는 시작 기호입니다. 규칙 α→β의 왼쪽 α에는 적어도 하나의 비단말 기호가 있어야 하며, 현재 문자열 xαy에서 α를 β로 바꾸면 xαy⇒xβy라고 씁니다.

구성 요소	역할	예
V	계속 치환할 수 있는 비단말 기호	{S,A}
T	최종 문자열에 남는 단말 기호	{a,b}
P	문자열을 바꾸는 생성 규칙	S→aSb, S→ab
S	유도를 시작하는 기호	S

유도는 비단말 기호가 없어질 때까지 규칙을 적용한다

P={S→aSb, S→ab}에서 aaabbb를 생성하려면 바깥의 a와 b를 두 번 늘린 뒤 마지막 S를 ab로 바꿉니다.

S ⇒ aSb ⇒ aaSbb ⇒ aaabbb

⇒^*는 규칙을 0회 이상 적용해 도달할 수 있음을 뜻합니다. 문법이 생성하는 언어는 L(G)={w∈T^* | S⇒^*w}입니다. 최종 결과에 비단말 기호가 남아 있으면 유도 중간 문자열일 뿐 언어의 원소가 아닙니다.

규칙 모양은 개수 사이의 관계를 만든다

• {a^mbⁿ | m,n≥0}: S→aS | Sb | λ. a와 b의 수를 서로 독립적으로 늘립니다.
• {aⁿbⁿ | n≥0}: S→aSb | λ. 규칙 한 번마다 양쪽에 a와 b가 하나씩 늘어 개수가 같습니다.
• {aⁿb^m | n≤m≤3n}: S→aSb | aSbb | aSbbb | λ. a 하나를 만들 때 b를 1개부터 3개까지 함께 만듭니다.

예를 들어 두 번째 문법에서 aabb는 S⇒aSb⇒aaSbb⇒aabb로 유도됩니다. 세 번째 문법에서는 각 단계가 a 하나와 b 1∼3개를 짝지으므로 전체 b의 수가 a의 수 이상이면서 세 배 이하라는 범위가 자동으로 유지됩니다.

검산 방법: 후보 문법이 목표 언어를 만든다는 주장에는 두 방향이 필요합니다. 규칙으로 만든 모든 문자열이 조건을 만족하는지 확인하고, 조건을 만족하는 임의의 문자열을 규칙으로 실제 생성할 수 있는지도 살펴야 합니다.

촘스키 계층은 규칙의 제한과 인식 장치를 연결한다

촘스키 계층은 생성 규칙을 얼마나 제한하는지에 따라 문법과 언어를 네 유형으로 분류합니다. 번호가 커질수록 규칙은 더 제한되고 언어의 범위는 좁아집니다. 따라서 정규 언어⊂문맥 자유 언어⊂문맥 의존 언어⊂재귀 열거 언어의 포함 관계가 성립합니다.

유형	문법	대표 규칙 제한	대응 인식 장치
제0유형	무제약 문법	α→β, α∈(V∪T)+, β∈(V∪T)*	튜링 기계
제1유형	문맥 의존 문법	α→β에서 |α|≤|β|	선형 한정 오토마톤
제2유형	문맥 자유 문법	A→β, A∈V	비결정적 푸시다운 오토마톤
제3유형	정규 문법	A→α 또는 A→αB의 선형 형태	유한 오토마톤

문맥 의존 문법은 생성 규칙을 적용해 문자열 길이가 줄어들지 않도록 제한합니다. 문맥 자유 문법은 왼쪽이 비단말 기호 하나여야 하므로 주변 문맥과 상관없이 그 기호를 치환할 수 있습니다. 정규 문법은 오른쪽에 비단말 기호가 하나 이하만 나타나고 그 위치도 제한되는 우선형 또는 좌선형 문법입니다.

계층 문제는 규칙의 겉모양만 한 줄 보고 가장 넓은 유형으로 답하지 않습니다. 예를 들어 모든 정규 문법은 문맥 자유 문법의 조건도 만족하지만, 분류에서는 그 문법이 만족하는 가장 제한적인 유형을 찾습니다. A→aB 또는 A→a 같은 우선형 규칙들로만 이루어졌다면 제3유형입니다.

연결 기억법: 유한 오토마톤↔정규 문법, 푸시다운 오토마톤↔문맥 자유 문법, 선형 한정 오토마톤↔문맥 의존 문법, 튜링 기계↔무제약 문법의 네 쌍을 규칙의 자유도가 커지는 방향으로 함께 정리하십시오.

상태·확률·규칙을 오갈 때의 재구성 순서

1. 상태 기계에서는 상태 집합, 입력 알파벳, 초기 상태와 최종 상태를 먼저 표시합니다.
2. DFA는 입력마다 현재 상태 하나를, NFA는 ε-폐쇄를 포함한 가능한 상태 집합을 갱신합니다.
3. 마르코프 전이행렬에서는 i행 j열이 i→j인지 확인하고 각 행의 합을 1로 검산합니다.
4. 여러 단계 확률은 중간 상태별 경로의 곱을 모두 더하거나 P의 거듭제곱으로 계산합니다.
5. 형식 언어에서는 λ의 포함 여부와 연결 순서를 먼저 확인합니다.
6. 문법 유도에서는 규칙을 적용한 위치를 표시하고 최종 문자열에 비단말 기호가 남지 않았는지 확인합니다.
7. 촘스키 유형은 각 생성 규칙이 만족하는 가장 강한 제한과 대응 인식 장치를 함께 판정합니다.

핵심 개념 정리

• 유한 오토마타는 현재 상태와 입력으로 전이하며, 입력을 모두 읽은 뒤 최종 상태에 있으면 문자열을 받아들입니다.
• DFA의 다음 상태는 하나지만 NFA는 여러 상태와 ε-전이를 허용하며, 성공하는 경로가 하나라도 있으면 받아들입니다.
• 마르코프 연쇄는 현재 상태에만 의존하는 확률 전이를 사용하고, n단계 전이는 Pⁿ으로 계산합니다.
• Σ^*는 빈 문자열을 포함하며, 언어 연결은 문자열 순서를 보존하므로 일반적으로 교환법칙이 성립하지 않습니다.
• 형식 문법은 G=(V,T,P,S)로 언어를 생성하고, 촘스키 계층은 생성 규칙의 제한을 인식 장치와 연결합니다.

14강을 하나의 흐름으로 복습하려면 ‘현재 상태에서 다음 상태로’라는 공통 틀을 유지하십시오. 결정적 전이는 한 상태를, 비결정적 전이는 가능한 상태 집합을, 확률적 전이는 분포를 갱신합니다. 이어서 인식된 문자열들의 집합을 언어로 보고, 반대 방향에서 문법 규칙으로 그 언어를 생성해 보면 오토마타와 형식 언어의 관계가 한 장의 지도처럼 연결됩니다.

예상문제 10선

1. 출력이 있는 유한 오토마타 M=(I,O,Q,f,g,σ)에서 f의 역할로 옳은 것은?

① 현재 상태와 입력 기호로 다음 상태를 정한다. ② 받아들일 문자열 전체를 미리 나열한다. ③ 최종 상태의 집합을 정한다. ④ 입력 기호를 출력 기호로만 바꾼다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: 전이 함수 f:Q×I→Q는 현재 상태와 입력을 다음 상태에 대응시킵니다.
• ② 오답: 언어는 기계가 입력을 처리한 결과로 정해지며 f가 문자열 목록을 저장하는 것은 아닙니다.
• ③ 오답: 최종 상태 집합은 언어 인식 모형의 F가 담당합니다.
• ④ 오답: 출력 기호를 정하는 함수는 g이며 f는 상태를 바꿉니다.

2. s₀가 초기 상태이고 0을 읽으면 s₁, s₁에서 0을 읽으면 최종 상태 s₂, 어느 상태에서든 1을 읽으면 s₀로 가는 DFA가 받아들이는 문자열은?

① 10101 ② 11010 ③ 01100 ④ 00101

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 마지막 1이 현재 상태를 s₀로 되돌려 최종 상태에서 끝나지 않습니다.
• ② 오답: 끝의 0이 하나뿐이므로 s₁에서 입력 처리가 끝납니다.
• ③ 정답: 마지막 두 0을 연속으로 읽어 s₀→s₁→s₂가 되므로 받아들입니다.
• ④ 오답: 앞에서 s₂에 도달해도 뒤의 1로 s₀에 돌아오므로 최종 판정은 거부입니다.

3. DFA와 NFA의 차이를 가장 정확히 설명한 것은?

① DFA는 최종 상태가 없고 NFA에만 최종 상태가 있다. ② NFA는 입력 기호의 순서를 자유롭게 바꿔 읽을 수 있다. ③ NFA는 입력을 일부 남긴 채 최종 상태에 닿아도 받아들인다. ④ NFA는 여러 다음 상태와 ε-전이를 허용하며 성공 경로 하나가 있으면 받아들인다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: DFA와 NFA 모두 입력을 모두 읽은 뒤 수용 여부를 판정하는 최종 상태를 사용합니다.
• ② 오답: 비결정성은 경로 선택에 관한 것이며 입력 기호의 순서는 그대로 유지됩니다.
• ③ 오답: 받아들이려면 선택한 경로가 입력 전체를 소비해야 합니다.
• ④ 정답: 다음 상태의 집합과 입력을 소비하지 않는 ε-전이가 NFA의 핵심 특징입니다.

4. 0을 원하는 만큼 읽고, 이어서 1을 원하는 만큼 읽으며 ε-전이로 두 구간을 건너뛸 수 있는 NFA가 받아들이는 문자열은?

① 101 ② 00011 ③ 1100 ④ 0101

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 1 구간으로 이동한 뒤 다시 0 구간으로 돌아갈 수 없습니다.
• ② 정답: 0 세 개 뒤에 1 두 개가 이어지는 0ⁿ1ᵐ 형태입니다.
• ③ 오답: 1 다음에 0이 나타나므로 정해진 구간 순서와 반대입니다.
• ④ 오답: 0과 1이 번갈아 나타나 두 구간만으로 처리할 수 없습니다.

5. P=[[0.826,0.174],[0.600,0.400]]에서 현재 상태가 1일 때 두 단계 뒤 상태 0일 확률은?

① 0.600 ② 0.7356 ③ 0.4956 ④ 1.226

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

• ① 오답: 한 단계 전이확률 p₁₀만 사용해 두 단계 조건을 반영하지 않았습니다.
• ② 정답: 1→0→0과 1→1→0을 합해 0.600×0.826+0.400×0.600=0.7356입니다.
• ③ 오답: 1→0→0 한 경로만 계산하고 중간 상태가 1인 경로를 빠뜨렸습니다.
• ④ 오답: 확률은 1을 넘을 수 없으며 경로확률은 더하기 전에 각 경로 안에서 곱해야 합니다.

6. 현재 상태 0에서 두 단계 뒤 상태 1로 갈 확률을 0.174×0.400=0.0696으로만 계산한 풀이에서 누락한 경로는?

① 0→1→0 ② 1→0→1 ③ 1→1→0 ④ 0→0→1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 이 경로는 최종 상태가 0이므로 구하려는 사건에 포함되지 않습니다.
• ② 오답: 시작 상태가 1이라 문제의 출발 조건과 다릅니다.
• ③ 오답: 시작과 끝이 모두 문제의 조건과 반대입니다.
• ④ 정답: 0→0→1의 확률 0.826×0.174를 더해야 총확률이 0.213324가 됩니다.

7. Σ={0,1}일 때 Σ^*에는 포함되지만 Σ⁺에는 포함되지 않는 것은?

① 0 ② 01 ③ λ ④ 110

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 길이 1인 문자열은 Σ⁺와 Σ*에 모두 포함됩니다.
• ② 오답: 길이 2인 이진 문자열도 두 집합 모두의 원소입니다.
• ③ 정답: Σ*는 Σ⁰={λ}를 포함하지만 Σ⁺는 길이 1 이상만 모읍니다.
• ④ 오답: 길이 3인 이진 문자열이므로 Σ⁺와 Σ*에 모두 포함됩니다.

8. 문법 P={S→aSb, S→ab}로 aaabbb를 유도한 과정으로 옳은 것은?

① S⇒aSb⇒aaSbb⇒aaabbb ② S⇒ab⇒aabb⇒aaabbb ③ S⇒aSb⇒aabSb⇒aaabbb ④ S⇒aSb⇒aaaSbbb⇒aaabbb

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

• ① 정답: S→aSb를 두 번의 바깥 확장에 사용하고 마지막 S→ab로 단말 문자열을 만듭니다.
• ② 오답: ab에는 비단말 기호가 없으므로 이후 규칙을 적용해 문자열을 늘릴 수 없습니다.
• ③ 오답: 주어진 규칙에는 S를 abS로 바꾸는 규칙이 없습니다.
• ④ 오답: 두 번째 화살표는 S→aSb 한 번으로 a와 b를 각각 두 개씩 늘려 허용된 한 단계가 아닙니다.

9. A→aB 또는 A→a와 같은 우선형 규칙으로만 이루어진 문법과 대응 인식 장치의 연결은?

① 제0유형 무제약 문법 — 튜링 기계 ② 제1유형 문맥 의존 문법 — 선형 한정 오토마톤 ③ 제2유형 문맥 자유 문법 — 푸시다운 오토마톤 ④ 제3유형 정규 문법 — 유한 오토마톤

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

• ① 오답: 우선형 규칙은 무제약 문법보다 훨씬 강한 제한을 만족하므로 가장 좁은 유형을 골라야 합니다.
• ② 오답: 길이가 줄지 않는다는 조건보다 비단말 위치까지 더 엄격하게 제한되어 있습니다.
• ③ 오답: 문맥 자유 문법 조건도 만족하지만 우선형이라는 추가 제한으로 제3유형에 속합니다.
• ④ 정답: 우선형·좌선형 문법은 정규 문법이며 유한 오토마톤이 인식하는 정규 언어와 대응합니다.

10. 14강의 개념 관계를 올바르게 연결한 것은?

① 마르코프 연쇄는 모든 과거 상태를 반드시 저장해야 다음 상태를 정한다. ② 형식 문법은 오직 주어진 문자열을 받아들일지 판정하고 문자열을 생성하지 않는다. ③ 오토마타는 언어를 인식하고 문법은 언어를 생성하며, 규칙 제한은 촘스키 계층으로 정리된다. ④ 정규 언어는 문맥 자유 언어보다 넓어 모든 문맥 자유 언어를 포함한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

• ① 오답: 마르코프 성질은 현재 상태가 주어지면 다음 상태 확률이 더 이전의 이력에 의존하지 않는다는 뜻입니다.
• ② 오답: 형식 문법은 시작 기호에 생성 규칙을 적용해 언어의 문자열을 만들어 냅니다.
• ③ 정답: 인식과 생성은 언어를 보는 두 방향이며 촘스키 계층이 문법 제한과 인식 장치를 대응시킵니다.
• ④ 오답: 포함 방향은 정규 언어⊂문맥 자유 언어이므로 반대입니다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 상태 전이 추적, 확률 경로합, 문법 유도와 강의자료 수치의 교차 검산은 학습자의 이해를 돕도록 구성하고 검토했습니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 컴퓨터과학과, 이산수학 제14강 「오토마타와 형식 언어」 강의자료(2021)
• 자료 범위: 유한 오토마타, 결정적·비결정적 유한 오토마타, 마르코프 연쇄, 형식 언어와 문법, 촘스키 계층
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-09-06