형식언어(formal language)는 언어의 생성 및 인식을 위한 수학적 도구로서 무한한 언어를 유한하게 표기할 수 있는 문자열 집합(symbolic string set)이다. 따라서 형식언어의 주제는 무한한 언어를 유한하게 서술하는 방법을 찾아내는 것이다. 이러한 방법은 대입 시스템(rewriting system)인 생성기와 인식기에 의하여 서술될 수 있다.
형식언어는 자연어와 마찬가지로 다음과 같이 3가지 기본요소로 정의할 수 있다.
1) 언어의 기본 요소인 알파벳 문자의 유한한 집합(finite symbol set)
2) 문자로 구성되는 문자열의 유한한 집합(finite string set)
3) 문자열을 구성하는 형식적 규칙의 유한한 집합(finite formal rule set)
이처럼 정의된 형식언어의 문장은 대입 시스템의 출발문자로부터 시작하여 특정한 문자열에 적합한 생성규칙(production rule)을 대입해가면서 얻어낸 일련의 문자열이다. 이때 만약 문장이 유한한 문자열 집합의 한 원소라면 이 문자열을 문법에 맞는 문장(well-formed sentence)이라고 한다. 여기서 문장형식을 결정 또는 생성하는 규칙(finite formal rule set)을 언어의 문법(구문) 이라고 한다.
이러한 원칙에 따라 형식언어를 정의해 보자. 여기서 →는 좌변의 문자를 우변의 문자로 대입하는 것을 의미한다.
finite symbol set={ A, 0, 1 }
finite string set={ 0∪1 }*
finite formal rule set={ A → 0A0, A → 1A1, A → 00, A → λ }
위에 정의된 언어로 생성된 문자열 1001111001은 문법에 맞는 문장(well-formed sentence)에 속한다. 왜냐면 1001111001∈{ 0∪1 }*이기 때문이다.
▶▷ 대입 시스템(Rewriting System) RW=(V, F)
V : 알파벳 집합
F : V에 관하여 쌍을 이루는 단어(word)의 유한한 집합으로서 이는 곧
단어를 생성 또는 인식하는 대입 규칙(rewriting rule)이다.
만약 P, Q∈V*라면, 이에 대하여 P → Q∈F로 표기한다.
오토마타(automata)란 명령을 엔코딩(encoding)에 대하여 답하거나, 연산의 이미 결정된 순차를 자동적으로 따르도록 설계된 제어기 또는 머신이라고 한다. 여기서 머신이라는 단어는 하드웨어적이라기 보다 주어진 심벌의 변화( 상태변화)를 형식적으로 서술할 수 있는 수학적 모델로 관찰된다. 따라서 오토마타는 입력에 대하여 정보를 처리하고 답하는 수학적 장치(device)라 할 수 있다.
오토마타는 입력장치(input unit), 처리장치(process unit), 출력장치(output unit)로 구성되는데 이들의 기능은 주어진 환경과 시간에 따라 행위를 결정하는 상태로 표기된다. 이때 상태는 프로그램에서 실행진로를 결정하는 요소로서 상태의 변화는 방향성 그래프(Digraph)로 표현되거나, 인접 리스트(adjacency list)로 구현될 수 있다. 따라서 그래프적 오토마타는 심벌취급과 프로세스(process)를 단순하고 우아하게 서술하기 위한 도구로서, 인식(recognize/accept), 생성(generating), 계산(computing) 기능을 기본적으로 갖는다.
형식언어의 관점에서 오토마타는 인식기로, 때로는 언어의 전환장치로서 이해된다.
무제약 문법을 인식할 수 있는 것은 무한 테이프를 이용한 튜링머신(Turing Machine) 이고, 문맥의존문법을 인식할 수 있는 것은 유한 테이프를 이용한 선형유계 오토마타(Linear Bounded Automata)이고 문맥자유문법을 인식할 수 있는 것은 스택을 이용하는 푸쉬다운 오토마타(Push Down Automata)이고, 정규문법을 인식할 수 있는 것은 시작상태에서 최종상태로 전이하는 유한오토마타(Finite Automata)이다.
유한 오토마타는 현실적으로 제한된 TM의 한 실용적 유형으로 관찰될 수 있는 장치로서 TM과는 달리 테이프의 자료를 읽은 후에 선택의 여지없이 헤드가 자동적으로 우측 한 방향으로 만 움직이는 특성을 갖는다. 한 방향으로 움직이는 개념은 양방향보다 기능면에서 제한된 느낌을 가질 수 있으나 사실상 양방향의 진행행위가 오토마타의 능력을 강화시키는 것만은 아니다. FA는 자료의 읽는 행위와 쓰는 행위에 의하여 구분되는데 테이프에서 단순히 자료를 읽는 기능을 갖는 FA를 인식기(finite automata recognizer)라 하고, 이와 더불어 자료를 테이프에 기록하는 기능도 갖는 FA를 생성기(generalized sequential machine)라고 한다.
▶▷ FA=(Q, Σ, q0, F, δ)
Q : 상태(state) 문자집합
Σ : 테이프(tape) 입력 문자집합
q0: q0⊂Q로서 출발상태 문자집합
F : F⊂Q로서 종료상태 문자집합
δ : Q × Σ → Q
푸쉬다운 오토마타는 FA보다 큰 언어를 인식할 수 있는 오토마타로써 이는 본질적으로 언어인식을 위해서 유한한 제어와 무한한 메모리를 갖추고 있다. PDA는 FA에 비하여 "push down store"라는 보조 메모리를 추가로 장치하고 있는데, PDA에서 입력테이프의 모든 작용은 FA와 동일하다. 특별히 이 메모리 장치는 스택 기능을 갖추고 있어서 push와 pop의 연산동작이 가능하다.
▶▷ Push-Down Automata(PDA)와 언어 L(PDA)
PDA=(Q, Σ, P, δ, q0, z0, F)
Q : 상태 문자의 집합(state symbol set)
Σ : 테이프의 입력문자의 집합(tape input symbol set)
P : 스택문자 집합(stack symbol set)
q0∈Q : 테이프의 출발상태(start state)
z0∈P : 스택의 출발문자(start symbol)
F⊂Q : 테이프의 종료상태의 집합(end-state set)
이때 Σ∩P≠0, Q∩(Σ∪P)=0 이고,
δ : Q × (Σ∪{λ}) × P → Q × P* 는 다음과 같은 기능을 갖는다.
i) δ(q1, a, z)=(q2, r) : 상태 q1에서 테이프의 문자 a를 읽은 후에
상태를 q2로 전이하고, 테이프 헤드를 우로 이동하며, 스택에서 읽은 문자 z을 r로 대치한다.
그리고 스택 헤드는 top에 위치시킨다.
ii) δ(q1, ε, z)=(q2, r) : 상태 q1에서 테이프의 내용과는 관계없이 q2로 전이하고,
테이프 헤드는 정지상태에 머문다. 그리고 스택문자 z을 r로 대치한다.
iii) δ(q1, a, z)=(q2, ε) : 상태 q1에서 테이프의 문자 a를 읽은 후에, 상태를 q2로 전이하고
테이프 헤드를 우로 이동한다. 그리고 스택에서 읽은 문자 z을 pop 한다 .
L(PDA)={P∈W(Σ)｜s0Pz0 ⇒* Qs1, Q∈W(Σ), s1∈F}
참고
http://user.chollian.net/~cyj1010/jongyun/dacu21.htm
댓글 없음:
댓글 쓰기