방송대 방통대 이산수학 14강 - 오토마타와 형식 언어 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 14강 - 오토마타와 형식 언어

오토마타와 튜링 머신의 의미를 살펴보고 유한 오토마타, 결정적 유한 오토마타, 비결정적 유한 오토마타의 구성과 문자열 수락 방법을 익힌다. 이어 마르코프 연쇄의 전이확률과 n단계 전이를 계산하고, 형식 언어·형식 문법·촘스키 계층의 관계를 체계적으로 정리한다.

제1장 오토마타와 계산의 추상화

1. 오토마타의 의미

오토마타(automata)는 스스로 움직이는 기계 또는 자동 장치를 뜻한다. 이산수학과 컴퓨터과학에서는 입력을 받아 정해진 규칙에 따라 상태를 바꾸고 결과를 내는 추상적 기계로 이해한다. 실제 컴퓨터도 한 시점에 유한한 상태 중 하나를 가지며 입력에 따라 다음 상태로 이동한다는 점에서 유한 상태 오토마타로 모델링할 수 있다.

오토마타 모델은 장치의 물리적 세부 구조를 모두 표현하지 않는다. 입력, 현재 상태, 전이 규칙, 출력 또는 수락 여부처럼 계산에 필요한 핵심만 남긴다. 이 추상화 덕분에 자동판매기, 개찰구, 리모컨, 문자열 판별기 등 서로 다른 시스템을 같은 수학적 틀로 분석할 수 있다.

2. 튜링 머신

튜링 머신(Turing machine)은 인간의 계산 과정을 구현한 추상적 오토마타이며 컴퓨터의 수학적 모델이다. 기호를 저장하는 무한 테이프와 테이프의 한 칸을 읽고 쓰는 헤드, 현재 상태를 보관하는 상태 레지스터, 수행 규칙을 담은 유한한 표로 구성된다.

구성 요소	역할
무한 메모리 테이프	여러 셀에 기호를 저장한다.
헤드	현재 셀의 기호를 읽고 새 기호를 쓴다.
상태 레지스터	현재 수행 상태를 기억한다.
유한 규칙표	기호 기록, 좌우 한 칸 이동, 다음 상태 이동 또는 정지를 지시한다.

튜링 머신은 컴퓨터로 계산할 수 있는 것의 범위를 설명하는 수학적 모델이다. 강의록에서는 “튜링 머신으로 모델링할 수 없는 문제는 컴퓨터로도 해결할 수 없다”는 관점으로 그 중요성을 강조한다.

3. 오토마타, 형식 언어, 형식 문법

형식 언어(formal language)는 프로그래밍 언어가 가진 일반적 특성을 기호와 문자열의 집합으로 추상화한 개념이다. 형식 문법(formal grammar)은 그러한 문자열을 만들어 내는 생성 규칙을 추상화한 것이다. 오토마타는 문자열을 인식하고, 문법은 문자열을 생성한다.

노엄 촘스키는 형식 문법, 형식 언어, 이를 인식하는 오토마타의 관계를 촘스키 계층으로 정리하였다. 제0유형에서 제3유형으로 갈수록 생성 규칙에 더 강한 제약이 붙으며, 이에 대응하는 언어와 오토마타의 능력도 달라진다.

제2장 유한 오토마타

1. 상태와 상태전이

유한 오토마타는 유한한 상태 중 하나를 현재 상태로 가지며 입력을 받을 때 다음 상태로 전이하고 출력을 만든다. 개찰구를 예로 들면 잠김과 열림이 상태이고, 동전 투입과 밀기가 입력이며, 파란불과 빨간불이 출력이다. 현재 상태와 같은 입력이라도 규칙에 따라 다음 상태와 출력이 달라질 수 있다.

상태 그래프, 상태도, 상태전이도는 이 동작을 방향 그래프로 표현한다. 원은 상태, 화살표는 전이를 나타내며, 화살표에는 보통 입력과 출력을 표시한다. 초기 상태는 외부에서 들어오는 화살표로 나타낸다.

2. 유한 오토마타의 6-튜플

강의에서 출력이 있는 유한 오토마타 M은 다음 여섯 요소로 정의된다.

M = (I, O, Q, f, g, σ)
I: 입력 기호의 유한집합
O: 출력 기호의 유한집합
Q: 상태의 유한집합
f: Q × I → Q인 전이함수
g: Q × I → O인 출력함수
σ: Q에 속하는 초기 상태

전이함수 f는 현재 상태와 입력을 받아 다음 상태를 정하고, 출력함수 g는 현재 상태와 입력을 받아 출력 기호를 정한다. 따라서 상태전이표에서 현재 상태와 입력을 찾으면 다음 상태와 출력이 하나씩 결정된다.

3. TV 채널 오토마타 예제

채널 7, 9, 11을 가진 TV에서 위 버튼 U와 아래 버튼 D를 입력으로 삼으면 I = {U, D}, Q = {7, 9, 11}이다. TV를 켰을 때 채널 7에서 시작하므로 σ = 7이다. 위 이동, 아래 이동, 이동 없음의 출력을 u, d, n으로 표시하면 O = {u, d, n}이다.

채널 7에서 D를 눌러도 7에 머물고 출력은 n이며, 채널 11에서 U를 눌러도 11에 머물고 출력은 n이다. 나머지 경우에는 U가 상위 채널로, D가 하위 채널로 이동한다. 상태전이표와 상태 그래프는 같은 정보를 표와 그림이라는 다른 방식으로 나타낸다.

4. 입력 문자열과 출력 문자열

입력 문자열을 처리할 때는 초기 상태에서 출발하여 입력 기호를 왼쪽부터 하나씩 읽는다. 각 단계에서 f로 다음 상태를 정하고 g로 출력 기호를 기록한다. 강의록 예제의 입력 01000110은 주어진 전이·출력표를 따라 처리하면 출력 문자열 ababbaaa를 만든다.

상태 추적 문제에서는 ‘현재 상태 → 입력 확인 → 출력 기록 → 다음 상태 이동’을 한 단계씩 표로 적으면 실수를 줄일 수 있다.

제3장 DFA와 NFA

1. 결정적 유한 오토마타

결정적 유한 오토마타(DFA) M = (I, Q, f, F, σ)는 입력기호 집합 I, 상태집합 Q, 전이함수 f, 수락상태집합 F, 초기상태 σ의 5-튜플이다. 전이함수는 f: Q × I → Q이다. 즉 현재 상태와 입력 기호가 주어지면 다음 상태가 정확히 하나로 결정된다.

수락상태는 상태 그래프에서 이중 원으로 표시한다. 입력 문자열의 모든 기호를 처리한 뒤 도달한 현재 상태가 F에 속하면 DFA가 그 문자열을 수락한다. 처리 중간에 수락상태를 지났더라도 마지막 상태가 수락상태가 아니면 수락하지 않는다.

2. 비결정적 유한 오토마타

비결정적 유한 오토마타(NFA)도 M = (I, Q, f, F, σ)의 5-튜플이지만 전이함수는 f: Q × (I ∪ {ε}) → P(Q)이다. 전이 결과가 Q의 한 원소가 아니라 Q의 부분집합이므로 하나의 상태와 입력에서 여러 다음 상태가 가능하거나 다음 상태가 없을 수 있다.

ε-전이는 입력 기호를 소비하지 않고 상태를 옮기는 전이이다. NFA에서는 가능한 여러 전이 경로 가운데 입력 전체를 처리하고 수락상태에 도달하는 경로가 하나라도 존재하면 문자열을 수락한다.

구분	DFA	NFA
전이함수	f: Q × I → Q	f: Q × (I ∪ {ε}) → P(Q)
다음 상태	현재 상태와 입력마다 정확히 하나	0개, 1개 또는 여러 개 가능
ε-전이	사용하지 않음	사용 가능
수락 판정	유일한 처리 경로의 마지막 상태가 수락상태	가능한 경로 중 하나라도 수락상태에 도달

3. NFA가 인식하는 문자열

강의록의 NFA 예제는 초기 상태에서 ε-전이를 이용해 다음 상태로 이동하고, 0을 반복해서 읽은 뒤 다시 ε-전이하여 1을 반복해서 읽는다. 이 오토마타가 수락하는 언어는 {0ⁿ1^m | n, m은 0 이상의 정수}이다. n과 m이 0일 수도 있으므로 공 문자열 ε, 0만으로 이루어진 문자열, 1만으로 이루어진 문자열도 포함될 수 있다.

DFA와 NFA 모두 문자열의 수락 여부를 판정하지만 전이의 결정성에서 차이가 난다. DFA는 각 단계의 다음 상태가 하나이고, NFA는 가능한 상태들의 집합을 추적해야 한다.

제4장 마르코프 연쇄

1. 이산확률과정과 마르코프 성질

마르코프 연쇄(Markov chain)는 시간에 따른 상태전이를 확률로 표현하는 유한 오토마타의 특수한 형태이다. X_n을 이산 시간 n에서의 상태를 나타내는 확률변수라 하면 (X₁, X₂, …)는 이산 시간에 순차적으로 관측되는 확률변수의 모임, 즉 이산확률과정이다.

마르코프 연쇄의 핵심은 미래 상태가 과거의 전체 이력이 아니라 현재 상태에만 의존하는 마르코프 성질이다.

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

이 성질은 과거 상태를 모두 기억하지 않아도 현재 상태만 알면 다음 상태의 확률을 정할 수 있다는 뜻이므로 무기억성(memorylessness)이라고도 한다.

2. 전이확률과 정상성

상태집합 S에서 현재 상태 i로부터 다음 상태 j로 전이될 확률을 전이확률 p_ij = P(X_n+1 = j | X_n = i)로 쓴다. 모든 전이확률은 0 이상 1 이하이고, 하나의 현재 상태 i에서 가능한 모든 다음 상태로 갈 확률의 합은 1이다.

전이확률 p_ij가 시간 n에 따라 달라지지 않으면 전이확률의 정상성(stationarity)이 성립하며 이를 정상 마르코프 연쇄라 한다. 마르코프 성질은 과거 의존성에 관한 조건이고, 정상성은 전이확률이 시간에 따라 변하지 않는다는 조건이므로 구별해야 한다.

3. 전이확률행렬과 상태전이도

전이확률들을 행렬로 배열한 P = (p_ij)를 전이확률행렬이라고 한다. 행 i는 현재 상태, 열 j는 다음 상태이며 각 행의 합은 1이다. 상태전이도는 상태를 원으로, 전이를 화살표로 그리고 각 화살표에 전이확률을 표시한 것이다. 표현 방식은 유한 오토마타의 상태 그래프와 기본적으로 같다.

4. n단계 전이확률

현재 시각 m의 상태 i에서 n단계 뒤인 m + n 시각에 상태 j가 될 확률을 n단계 전이확률 p_ij⁽ⁿ⁾이라 한다. 중간 상태 k를 거치는 모든 가능성을 더하는 채프만-콜모고로프 방정식으로 계산할 수 있다.

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

따라서 n단계 전이확률행렬은 1단계 전이확률행렬 P의 n제곱이며, p_ij⁽ⁿ⁾은 Pⁿ의 (i, j) 원소이다. 웹 페이지 사이의 이동을 확률 전이로 나타내는 페이지 랭크 예제처럼 현재 분포에 전이행렬을 반복 적용하여 미래 상태 분포를 구할 수 있다.

제5장 형식 언어와 언어의 연산

1. 알파벳과 문자열

알파벳(alphabet) Σ는 공집합이 아닌 기호들의 유한집합이다. 알파벳의 기호들을 유한한 순서로 나열한 것을 문자열(string)이라고 한다. 아무 기호도 포함하지 않은 길이 0의 문자열은 공 문자열이며 λ 또는 ε로 표시한다.

예를 들어 Σ = {0, 1}이면 λ, 0, 1, 10, 010, 0001 등은 모두 Σ 위의 문자열이다. 문자열에서는 순서와 반복이 중요하므로 01과 10은 서로 다른 문자열이다.

2. Σⁿ, Σ⁺, Σ^*와 언어

기호	뜻	공 문자열 포함
Σn	길이가 정확히 n인 Σ 위의 모든 문자열	n = 0일 때 포함
Σ+	길이가 1 이상인 모든 문자열	포함하지 않음
Σ*	길이가 0 이상인 모든 문자열	포함함

언어(language)는 Σ^*의 임의의 부분집합이다. 언어는 유한할 수도 무한할 수도 있다. 예를 들어 {aⁿbⁿ | n ≥ 1}은 ab, aabb, aaabbb 등을 포함하는 언어이다.

Σ^* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ …이고 Σ⁺ = Σ¹ ∪ Σ² ∪ …이다. 두 집합의 차이는 공 문자열 하나이다.

3. 언어의 접속, 교집합, 합집합

두 언어 L₁, L₂의 접속은 L₁의 문자열 x 뒤에 L₂의 문자열 y를 붙인 모든 문자열의 집합으로, L₁L₂ = {xy | x ∈ L₁, y ∈ L₂}이다. 접속은 순서가 중요하므로 일반적으로 L₁L₂ ≠ L₂L₁이다.

교집합 L₁ ∩ L₂는 두 언어에 모두 속하는 문자열의 집합이고, 합집합 L₁ ∪ L₂는 둘 중 적어도 하나에 속하는 문자열의 집합이다. L = {0, 1}이면 L^*는 λ, 0, 1, 00, 01, 10, 11 등 모든 유한 이진 문자열을 포함하고, L⁺에서는 λ만 제외된다.

제6장 형식 문법과 유도

1. 구구조 문법의 구성

형식 문법은 유한개의 규칙으로 특정 언어의 문자열을 생성하거나 주어진 문자열이 그 언어에 속하는지를 판단하는 방법이다. 구구조 문법(phrase-structure grammar)은 G = (V, T, P, S)의 네 요소로 정의된다.

요소	의미
V	변수 또는 비단말 기호의 유한집합이며 보통 대문자로 쓴다.
T	최종 문자열을 구성하는 단말 기호의 유한집합이며 보통 소문자로 쓴다.
P	α → β 형태의 생성 규칙 집합이다. 좌변 α는 적어도 하나의 비단말 기호를 포함한다.
S	V에 속하는 시작 기호이다.

2. 유도

생성 규칙 α → β가 있고 x, y ∈ (V ∪ T)^*이면 문자열 xαy에서 α를 β로 바꿔 xβy를 만들 수 있다. 이를 xαy ⇒ xβy로 쓰고 한 단계 유도라고 한다. 여러 단계의 유도를 거쳐 a₁에서 a_n을 만들 수 있으면 a₁ ⇒^* a_n으로 나타낸다.

예를 들어 P = {S → aSb, S → ab}이면 S ⇒ aSb ⇒ aaSbb ⇒ aaabbb로 유도할 수 있다. 재귀 규칙 S → aSb를 적용할 때마다 a와 b가 하나씩 늘고, 마지막에 S → ab를 적용하여 비단말 기호를 제거한다.

3. 문법이 생성하는 언어

문법 G가 생성하는 언어 L(G)는 시작 기호 S로부터 유도할 수 있는 단말 기호만으로 이루어진 모든 문자열의 집합이다.

L(G) = {w ∈ T^* | S ⇒^* w}

예를 들어 V = {S, A}, T = {a, b}, P = {S → Ab, S → Aa, A → a}이면 S ⇒ Ab ⇒ ab 또는 S ⇒ Aa ⇒ aa가 가능하므로 L(G) = {aa, ab}이다.

4. 언어를 만드는 생성 규칙

언어 {a^mbⁿ | m, n ≥ 0}은 S → aS, S → Sb, S → λ로 생성할 수 있다. a와 b의 개수를 서로 독립적으로 늘린다. 반면 {aⁿbⁿ | n ≥ 0}은 S → aSb, S → λ로 생성하여 a와 b를 반드시 한 쌍씩 늘린다.

{aⁿb^m | n ≤ m ≤ 3n, n ≥ 0}을 생성하려면 a 하나를 만들 때 b를 1개, 2개 또는 3개 붙이도록 S → aSb, S → aSbb, S → aSbbb, S → λ를 사용한다. 생성 규칙의 형태가 문자열 개수 사이의 조건을 직접 반영한다.

제7장 촘스키 계층

촘스키 계층은 생성 규칙에 가하는 제약에 따라 문법과 언어를 네 유형으로 분류하고 각 언어를 인식하는 오토마타를 연결한다.

유형	문법	생성 규칙의 핵심	언어	대응 오토마타
제0유형	무제약 문법	α → β, α ∈ (V ∪ T)+, β ∈ (V ∪ T)*	재귀열거언어	튜링 머신
제1유형	문맥 의존 문법	α → β이고 |α| ≤ |β|	문맥 의존 언어	선형 유한 오토마타
제2유형	문맥 자유 문법	A → β, 좌변은 하나의 비단말 기호	문맥 자유 언어	비결정적 푸시다운 오토마타
제3유형	정규 문법	A → α 또는 A → αB, 우변의 비단말 기호는 하나 이하	정규 언어	유한 오토마타

1. 제0유형: 무제약 문법

무제약 문법은 α → β에서 좌변 α가 비어 있지 않고 적어도 하나의 비단말 기호를 포함한다는 기본 조건 외에는 강한 형식 제약이 없다. 생성되는 재귀열거언어는 튜링 머신과 대응한다.

2. 제1유형: 문맥 의존 문법

문맥 의존 문법에서는 생성 규칙 α → β에 대해 |α| ≤ |β|이므로 일반적으로 유도 과정에서 문자열 길이가 줄어들지 않는다. αAβ → αγβ, γ ≠ λ처럼 비단말 기호 A가 주변 문맥 α, β 안에서 치환된다는 의미를 가진다. 문맥 의존 언어는 선형 유한 오토마타와 대응한다.

3. 제2유형: 문맥 자유 문법

문맥 자유 문법은 생성 규칙의 좌변이 하나의 비단말 기호 A인 A → β 형태이다. A의 앞뒤에 어떤 기호가 있든 같은 규칙을 적용할 수 있으므로 문맥 자유라고 한다. 문맥 자유 언어는 비결정적 푸시다운 오토마타와 대응한다.

4. 제3유형: 정규 문법

정규 문법은 A → α 또는 A → αB 형태로, 우변에 나타나는 비단말 기호가 하나 이하이고 위치도 제한된다. 비단말 기호가 오른쪽에 놓이는 우선형 문법과 왼쪽에 놓이는 좌선형 문법이 있다. 정규 언어는 유한 오토마타가 인식한다.

제3유형 정규 문법은 제2유형 문맥 자유 문법의 특수한 경우이고, 제2유형은 제1유형보다 제한적이며, 제1유형은 제0유형보다 제한적이다. 계층 안쪽으로 갈수록 문법 규칙은 단순해지지만 표현할 수 있는 언어의 범위는 좁아진다.

핵심 개념 정리

• 오토마타는 입력과 현재 상태에 따라 상태를 전이하는 추상적 자동 장치이며, 튜링 머신은 컴퓨터의 계산 능력을 설명하는 수학적 모델이다.
• 출력이 있는 FA는 M = (I, O, Q, f, g, σ)의 6-튜플이며 전이함수와 출력함수를 가진다.
• DFA는 f: Q × I → Q이므로 다음 상태가 하나이고, NFA는 f: Q × (I ∪ {ε}) → P(Q)이므로 여러 상태와 ε-전이가 가능하다.
• 입력을 모두 처리한 뒤 DFA는 최종 상태가 수락상태이면 수락하고, NFA는 가능한 경로 중 하나라도 수락상태에 도달하면 수락한다.
• 마르코프 연쇄는 미래가 현재 상태에만 의존하는 무기억성을 가지며, 전이확률행렬의 각 행 합은 1이다.
• n단계 전이확률행렬은 P⁽ⁿ⁾ = Pⁿ이고 채프만-콜모고로프 방정식으로 중간 상태의 모든 경로를 합산한다.
• 알파벳은 유한한 기호 집합, 문자열은 기호의 유한한 나열, 언어는 Σ^*의 부분집합이다.
• Σ^*는 공 문자열을 포함하지만 Σ⁺는 포함하지 않으며, 언어의 접속은 일반적으로 교환법칙이 성립하지 않는다.
• 문법 G = (V, T, P, S)가 생성하는 언어는 L(G) = {w ∈ T^* | S ⇒^* w}이다.
• 촘스키 계층은 무제약·문맥 의존·문맥 자유·정규 문법을 각각 튜링 머신·선형 유한 오토마타·비결정적 푸시다운 오토마타·유한 오토마타와 연결한다.

이 강의의 핵심 흐름은 ‘문법이 문자열을 생성하고, 오토마타가 언어의 문자열을 인식한다’는 관계이다. DFA와 NFA 문제에서는 전이함수의 공역과 ε-전이 가능 여부를 먼저 확인하고, 마르코프 연쇄에서는 행 방향 전이확률과 행 합 1, P의 거듭제곱을 점검한다. 형식 문법 문제는 시작 기호에서 단말 문자열까지의 유도를 추적하고 생성 규칙의 모양으로 촘스키 유형을 판별하면 된다.

예상문제 20선

1. 튜링 머신의 구성 요소가 아닌 것은?

① 기호를 저장하는 테이프 ② 기호를 읽고 쓰는 헤드 ③ 유한한 규칙표 ④ 전이확률의 정상성

정답입니다.

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

정답 및 해설 보기

정답: ④
전이확률의 정상성은 마르코프 연쇄의 개념이다. 튜링 머신은 테이프, 헤드, 상태 레지스터, 유한 규칙표로 구성된다.

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

① 초기 상태를 정한다. ② 현재 상태와 입력으로 출력 기호를 정한다. ③ 수락상태집합을 정한다. ④ 입력 기호의 집합을 만든다.

정답입니다.

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

정답 및 해설 보기

정답: ②
출력함수 g: Q × I → O는 현재 상태와 입력 기호에 대응하는 출력 기호를 결정한다.

3. DFA의 전이함수를 올바르게 나타낸 것은?

① f: Q × I → Q ② f: Q × I → O ③ f: Q → P(I) ④ f: I → F

정답입니다.

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

정답 및 해설 보기

정답: ①
DFA에서는 현재 상태와 입력 기호가 주어졌을 때 다음 상태 하나가 결정되므로 전이함수의 공역은 Q이다.

4. DFA가 입력 문자열을 수락하는 조건은?

① 첫 입력을 읽자마자 수락상태를 지나면 된다. ② 모든 상태를 한 번씩 방문해야 한다. ③ 입력을 모두 처리한 뒤 현재 상태가 수락상태이다. ④ ε-전이를 반드시 한 번 사용해야 한다.

정답입니다.

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

정답 및 해설 보기

정답: ③
DFA는 입력 기호 전체를 순서대로 처리한 최종 상태가 수락상태집합 F에 속할 때 문자열을 수락한다.

5. NFA의 ε-전이에 대한 설명으로 옳은 것은?

① 입력 문자열 전체를 지운다. ② 반드시 수락상태에서만 사용할 수 있다. ③ 다음 입력 기호 두 개를 동시에 소비한다. ④ 입력 기호를 소비하지 않고 상태를 전이한다.

정답입니다.

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

정답 및 해설 보기

정답: ④
ε-전이는 입력 문자열에서 기호를 읽지 않은 채 다른 상태로 이동하는 NFA의 전이이다.

6. NFA가 문자열을 수락하는 경우는?

① 가능한 전이 경로 중 하나라도 입력을 모두 처리하고 수락상태에 도달한다. ② 모든 가능한 경로가 같은 상태에서 끝나야 한다. ③ 전이 경로가 정확히 하나여야 한다. ④ 수락상태집합이 공집합이어야 한다.

정답입니다.

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

정답 및 해설 보기

정답: ①
NFA는 여러 전이 가능성을 허용하며 그중 수락에 성공하는 경로가 하나라도 있으면 문자열을 수락한다.

7. 마르코프 성질의 핵심 의미는?

① 미래 상태가 최초 상태에만 의존한다. ② 미래 상태가 현재 상태에만 영향을 받는다. ③ 모든 상태의 전이확률이 같다. ④ 상태가 시간에 따라 변하지 않는다.

정답입니다.

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

정답 및 해설 보기

정답: ②
마르코프 성질은 다음 상태의 조건부 확률이 전체 과거가 아니라 현재 상태만으로 결정된다는 무기억성이다.

8. 전이확률행렬 P에서 각 행의 원소 합은 얼마인가?

① 0 ② 상태 수 ③ 1 ④ 변의 수

정답입니다.

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

정답 및 해설 보기

정답: ③
현재 상태 i에서 다음 단계에 가능한 모든 상태로 전이할 확률을 합하면 반드시 1이다.

9. 전이확률의 정상성에 대한 설명으로 옳은 것은?

① p_ij가 시간의 변화에 무관하다. ② 모든 p_ij가 0이다. ③ 과거의 모든 상태를 기억해야 한다. ④ 상태전이가 일어나지 않는다.

정답입니다.

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

정답 및 해설 보기

정답: ①
정상성은 같은 i에서 j로의 전이확률이 어느 시점에서나 동일하다는 성질이다.

10. 정상 마르코프 연쇄의 n단계 전이확률행렬은?

① nP ② P + n ③ P / n ④ Pⁿ

정답입니다.

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

정답 및 해설 보기

정답: ④
채프만-콜모고로프 방정식에 따라 P⁽ⁿ⁾ = P^(n-1)P = Pⁿ이다.

11. Σ = {0, 1}일 때 공 문자열 λ에 대한 설명으로 옳은 것은?

① 길이가 1인 문자열이다. ② 기호 0 하나로 된 문자열이다. ③ 아무 기호도 포함하지 않은 길이 0의 문자열이다. ④ Σ^*에 포함되지 않는다.

정답입니다.

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

정답 및 해설 보기

정답: ③
공 문자열은 기호가 하나도 없는 길이 0의 문자열이며 Σ^*에는 포함되지만 Σ⁺에는 포함되지 않는다.

12. Σ⁺와 Σ^*의 차이를 올바르게 설명한 것은?

① Σ⁺만 공 문자열을 포함한다. ② Σ^*는 공 문자열을 포함하고 Σ⁺는 포함하지 않는다. ③ Σ⁺는 유한하고 Σ^*는 항상 공집합이다. ④ 두 집합은 모든 알파벳에서 항상 같다.

정답입니다.

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

정답 및 해설 보기

정답: ②
Σ⁺는 길이 1 이상, Σ^*는 길이 0 이상의 모든 문자열을 모으므로 공 문자열 포함 여부가 다르다.

13. L₁ = {a, aa}, L₂ = {b}일 때 L₁L₂는?

① {ba, baa} ② {a, aa, b} ③ {ab} ④ {ab, aab}

정답입니다.

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

정답 및 해설 보기

정답: ④
L₁의 각 문자열 뒤에 L₂의 b를 붙이므로 ab와 aab가 생성된다. 언어의 접속은 순서가 중요하다.

14. 구구조 문법 G = (V, T, P, S)에서 P가 나타내는 것은?

① 단말 기호의 집합 ② 생성 규칙의 집합 ③ 초기 확률의 집합 ④ 수락상태의 집합

정답입니다.

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

정답 및 해설 보기

정답: ②
V는 비단말 기호, T는 단말 기호, P는 생성 규칙, S는 시작 기호를 나타낸다.

15. P = {S → aSb, S → ab}에서 aaabbb를 유도한 과정은?

① S ⇒ aSb ⇒ aaSbb ⇒ aaabbb ② S ⇒ ab ⇒ aabb ⇒ aaabbb ③ S ⇒ Sa ⇒ Saa ⇒ aaabbb ④ S ⇒ bSa ⇒ bbSaa ⇒ aaabbb

정답입니다.

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

정답 및 해설 보기

정답: ①
S → aSb를 두 번 적용해 a와 b를 양쪽에 늘린 뒤 S → ab를 적용하면 aaabbb가 된다.

16. 문법 G가 생성하는 언어 L(G)의 정의로 옳은 것은?

① V에 속하는 모든 비단말 기호의 집합 ② 생성 규칙 P 자체의 집합 ③ S에서 유도 가능한 T^*의 모든 문자열 집합 ④ 유도 중 나타나는 비단말 문자열만의 집합

정답입니다.

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

정답 및 해설 보기

정답: ③
L(G)는 시작 기호 S로부터 유도할 수 있고 단말 기호만으로 이루어진 문자열 w들의 집합이다.

17. 생성 규칙의 좌변이 하나의 비단말 기호 A인 A → β 형태의 문법은?

① 무제약 문법 ② 문맥 자유 문법 ③ 마르코프 문법 ④ 전이확률 문법

정답입니다.

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

정답 및 해설 보기

정답: ②
제2유형 문맥 자유 문법은 좌변에 비단말 기호 하나만 오므로 주변 문맥과 관계없이 치환할 수 있다.

18. 문맥 의존 문법의 생성 규칙 α → β가 만족하는 길이 조건은?

① |α| ≤ |β| ② |α| > |β|만 가능 ③ |α| = 0 ④ |β| = 0만 가능

정답입니다.

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

정답 및 해설 보기

정답: ①
제1유형 문맥 의존 문법에서는 일반적으로 생성 규칙 적용 후 문자열 길이가 줄어들지 않는다.

19. 촘스키 계층에서 정규 언어를 인식하는 오토마타는?

① 튜링 머신만 가능하다. ② 선형 유한 오토마타 ③ 비결정적 푸시다운 오토마타 ④ 유한 오토마타

정답입니다.

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

정답 및 해설 보기

정답: ④
제3유형 정규 문법이 생성하는 정규 언어는 유한 오토마타가 인식한다.

20. 촘스키 계층의 연결이 옳은 것은?

① 제0유형 - 정규 문법 - 유한 오토마타 ② 제1유형 - 문맥 자유 문법 - 튜링 머신 ③ 제2유형 - 문맥 자유 문법 - 비결정적 푸시다운 오토마타 ④ 제3유형 - 무제약 문법 - 선형 유한 오토마타

정답입니다.

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

정답 및 해설 보기

정답: ③
제2유형은 문맥 자유 문법과 문맥 자유 언어이며 비결정적 푸시다운 오토마타에 대응한다.