Chomshy Hierarchy (촘스키 계층)

• Type 1 : No restrictions(unrestricted grammer)
• Type 2 : Context-sensitive grammar(CSG)
  a->b, |a| <= |b|
• Type 3 : Context-free grammar(CFG)
  A->a, A : nonterminal, a는 V*의 원소
• Type 4 : Regular ggrammar(RG)
  우선형 문법 또는 좌선형 문법 구조로만 생성이 되어야 한다.
  

언어는 생성규칙에 따라 재귀적인 방법으로 호출되며 생성되는데 위의 4가지로 분류될수있다.
Type이 높아질수록 언어 생성규칙에 제약이 많아진다.

REL (Recursively Enumerable Language) : Type1 문법으로 생성된 언어
CSL (Context Sensitive Language) : Type2 문법으로 생성된 언어, 람다문법이 없다.
CFL (Context Free Language) : Type3 문법으로 생성된 언어, 람다문법이 있다.
RL (Regular Language) : Type4 문법으로 생성된 언어

ex
L = {a^nb^n | n >= 0} : CFL
L = {ww^R | w은 sentence} : CFL
L = {w | w = w^R} : CFL
L = {a^nb^nc^n | n >= 1} : CSL

w^R은 w을 역순으로 만든 sentence 이다.

Recognizer

type 0 (unrestricted) : Turing Machine
type 1 (context-sensitive) : Linear Bounded Automata
type 2 (context-free) : Pushdown Automata
type 3 (regular language) : Finite Automata

---

정규언어와 정규문법

Type 3 정규문법을 통해 생성된 언어는 두가지 생성규칙으로 나뉜다.
1. 우선형 A -> tB, A -> t
2. 좌선형 A -> Bt, A -> t

L(G) = {a^ncb^n | n >= 0} 은 문자 c를 기준으로 좌우로 terminal 문자가 생성되므로 rl가 아니라 cfl이다.
L = {a^nb^m | n,m >= 1} 는 rl 이다. 다음과 같은 생성규칙을 가지면 만들수있다.
S -> aS | aA
A -> bA | b

우선형문법으로 정규문법 만들기

S -> abcA ||| S -> aS1, S1 -> bS2, S2 -> cA
A -> bcA ||| A -> bA1, A1 -> cA
A -> cd ||| A -> cA1, A1 -> d

terminal 하나와 nonterminal 하나씩 붙여서 여러번 반복시키면 된다!!

---

정규표현

regular expression
언어를 집합이라 생각해보자!!

L = {0}
$L\ =\ \left\{1\right\}$
$L\ =\ \left\{ε\right\}$
$L\ =\ \left\{\varnothing \right\}$

0
1
ε
∅ 로 표현할수있다.

또한 +,·,* 을 통해서 합집합, concatenation, closure 연산을 표현할수있다.

정규표현방정식으로 통해서도 정규표현을 구할수있다.
X = aX + b가 있다면
X의 최소해는 a*b이다.

ex)
S -> aA | bB | b, A -> bA | $\epsilon$, B -> bS

이러한 생성규칙을 가지는 문법을 정규표현으로 나타내보자.
S = aA + bB + b
A = bA + $\epsilon$ = b*
B = bS

A, B를 S에 대입해보면
S = bbS + ab* + b
= (bb)*(ab* + b) 이다.

---

유한 오토마타

FA(Finite Automata)는 정규언어를 인식할수있는 기계이다.
정규언어로 짜여진 언어를 이 기계에 입력하면 FA는 이것이 정규언어인지 아닌지 인식을 해준다.

상태라는 개념을 통해 initial state에서 input값을 하나씩 transition matrix에서 찾아 상태를 변경하며 input이 끝났을때 final state에서 끝났다면 input은 정규언어인 것이다.

G = (Vn, Vt, P, S) - nonterminal, terminal, 생성규칙, 시작 nonterminal
M = (Q, $\Sigma$, $\delta$, q0, F)

문법 G는 4개의 텀으로 구성되었다면 오토마타 M은 5개의 텀으로 구성된다.
Q - 유한 상태집합
$\Sigma$ - 유한 input alphabet
$\delta$ - mapping
q0 - start state
F - set of final state

---

DFA, NFA

유한 오토마타는 결정(DFA), 비결정(NFA) 두 개로 나뉜다.

결정적 오토마타는 어떤 상태에서 transition이 하나로만 이어진 경우,
비결정적 오토마타는 둘이상인 것이다.

즉 a상태에서 b라는 input이 들어온 경우 c로만 상태가 변화하면 결정적, c와 d, e등등으로 상태가 변화할수있으면 비결정적이다.

예
오토마타 M = {{p,q,r}, {0,1}, $\delta$, p, {r}} 이고
$\delta$(p,0) = q
$\delta$(p,1) = p
$\delta$(q,0) = r
$\delta$(q,1) = p
$\delta$(r,0) = r
$\delta$(r,1) = r
같은 변환식이 있을 때 1001을 input으로 넣어보자.

$\delta$(p, 1001) = $\delta$(p,001) = $\delta$(q,01) = $\delta$(r,1) = r
r은 final state set의 원소이므로 1001은 오토마타가 인식한 언어이다!!!

1010은 입력으로 넣으면 최종으로 q라는 상태로 가는데 이는 final state set의 원소가 아니므로 이는 오토마타 M이 인식하지 않는 언어이다.

---

convert NFA into DFA

크게 어렵지는 않다. 그냥 가능한 입력값에 해당하는 모든 상태를 묶어버리고 final state에 해당하는 상태가 있는 집합을 다 final state 취급하면 된다.

NFA

$\delta$(q0,0) = {q1, q2}
$\delta$(q0,1) = {q1, q3}
$\delta$(q1,0) = {q1, q2}
$\delta$(q1,1) = {q1, q3}
$\delta$(q2,0) = {qf}
$\delta$(q2,1) = null
$\delta$(q3,0) = null
$\delta$(q3,1) = {qf}
$\delta$(qf,0) = {qf}
$\delta$(qf,1) = {qf}

DFA

$\delta$(q0,0) = {q1q2}
$\delta$(q0,1) = {q1q3}
$\delta$(q1q2,0) = {q1q2qf}
$\delta$(q1q2,1) = {q1q3}
$\delta$(q1q3,0) = {q1q2}
$\delta$(q1q3,1) = {q1q3qf}
$\delta$(q1q2qf,0) = {q1q2qf}
$\delta$(q1q2qf,1) = {q1q3qf}
$\delta$(q1q3qf,0) = {q1q2qf}
$\delta$(q1q3qf,1) = {q1q3qf}

NFA 에서 q0가 입력0에 대해 갈수있는 상태는 q1,q2이다. 그래서 DFA에서는 상태 q1q2로 갈수있다고 적어버린다.
마찬가지로 q0에서 입력1에 대해 갈수있는 상태는 q1,q3이니 아예 묶어적어버린다.
그다음에 상태 q1q2에 대해서 입력0을 집어넣으면 상태 q1의 입력0에 대한 상태(q1,q3)와 상태 q2의 입력 0 에 대한 상태(qf)를 합치면 q1q3qf이다.
이런식으로 각각의 대한 상태를 다 합쳐버려서 쭉 진행하면 위와같은 DFA를 그릴수있고 qf가 들어있는 모든 상태들에서 종료가 가능하다.
그래서 DFA 의 종료상태 집합은 (q1q2qf, q1q3qf)이다.

정규문법, 정규표현, 정규표현방정식, transition diagram, fa은 서로서로 왔다가면서 표현가능하다.