regular language

정규언어는 토큰의 형태를 기술하는데 사용.
regular grammar(정규문법), regular expression(정규표현), finite automata(유한 오토마타)에 의해 표현한다.

정규문법 정의
A->aB 또는 A->a. A와 B는 논터미널, a는 터미널.
S ->ε이면 S가 다른 생성규칙의 오른쪽에 나타나지 않는다.
토큰의 구조를 표현하는데 사용. context-free문법으로도 만들 수 있지만 정규문법으로 더 쉽게 구현할 수 있다.
 
정규표현
기본 소자
Φ(공집합), ε(empty string을 나타내는 집합), terminal 심벌.  
union :  (e1)+(e2) 또는 (e1) | (e2)
concatenation : (e1)(e2)
closure : (e1)*

regular expression equation(정규표현식)
계수가 정규표현인 식.
정규문법을 정규표현식으로 나타낼 수 있고, 정규표현을 구할 수 있다.
정규문법과 정규표현은 같은 종류의 언어를 나타낸다.

유한오토마타
입력으로 스트링을 받아서 그 스트링이 그 언어의 문장이면 yes, 아니면 no을 답하는 인식기.
5개의 요소로 정의
유한개의 상태, 입력 심벌, 사상 함수(mapping function), 시작상태, 종결 상태(final state)
사상함수는 어떤 입력 a가 들어왔을 때, 상태 중에 하나를 결과(다음상태가 된다.)로 내보내는 함수. 전이함수라고 한다.

DFA(Deterministic FA)
전이 함수가 한 입력에 대한 다음 상태로 하나의 상태만을 갖는 경우. 

state transition diagram (상태 전이도)
유한 오토마타를 그림으로 나타낸것. 시작상태를 start, 각 상태는 노드,특히 종료 상태는 이중원인 노드. 입력에 대한 상태의 변화는 edges.

NFA (Non deterministic FA)
한 입력을 보고 다음 상태가 하나 이상 있을 수 있는 유한 오토마타.

NFA를 DFA로 바꿀 수 있다. NFA가 언어의 구조르 쉽게 표현할 수 있지만 프로그램으로 만들기는 어렵다. 그래서 DFA로 변환한다.
NFA에서 한 입력으로 갈 수 있는 노드들을 하나로 묶어서 하나의 상태로 본다.

ε-CLOSURE(s)
NFA에서 입력으로 ε을 가질 수 있을 때, 하나의 상태 s가 ε입력으로 갈 수 있는 모든 상태들의 집합.

DFA state minimization ( DFA 상태수 최소화)
종결상태와 종결아닌 상태로 나누고
각 그룹에서 할 일은 그룹에 있는 상태들이 각 입력에 대해 어느 그룹으로 가는지 조사하고 같은 그룹으로  가는 것들끼리 또 나누는 것.

정규문법을 유한 오토마타로 바꿀 수 있고,
유한 오토마타를 정규문법으로 바꿀 수 있다.

유한 오토마타가 인식하는 언어를 정규표현으로 나타낼 수 있다.
먼저 유한 오토마타로 정규문법을 구하고 그걸로 정규 표현을 얻는다.
또는 정규표현으로 유한 오토마타를 구할 수 있다.
정규 표현의 기본 소자(union, concatenation, closure 등)을 NFA로 표현하고, 간단화하고 DFA으로 변환한다.

펌핑 렘마
어떤 언어가 정규 언어가 아님을 증명하는데 사용.