Regular Grammar는 Production Rule의 형태를 제한하여 Finite Automaton과 같은 Language Class를 생성하는 Grammar이다. 일반적으로 Right-linear Grammar 또는 Left-linear Grammar를 사용한다.
Right-linear Grammar
Production이 다음 형태를 가진다.
여기서 , 이다. Variable이 있다면 오른쪽 끝에 하나만 나타난다.
예를 들어
는 처음 1이 나온 뒤 최종 1로 끝나는 구조를 만든다.
Left-linear Grammar
Production이 다음 형태를 가진다.
Variable이 왼쪽 끝에 나타난다. Right-linear와 Left-linear Grammar는 각각 Regular Language를 생성한다. 그러나 두 형태를 한 Grammar에서 무제한으로 섞으면 Regular Language보다 강한 Language가 생성될 수 있으므로 주의해야 한다.
Right-linear Grammar에서 NFA로
각 Variable을 NFA State로 만든다. 별도의 Accept State 를 추가할 수 있다.
- 는 Transition 로 만든다.
- 는 로 만든다.
- 이면 를 Accept State로 둔다.
- Start Variable이 NFA Start State이다.
NFA에서 Right-linear Grammar로
NFA의 각 State에 대응하는 Variable을 만든다.
- Transition 마다 를 추가한다.
- Accept State 마다 를 추가한다.
- NFA Start State에 대응하는 Variable을 Start Variable로 둔다.
예제
다음 Grammar를 생각한다.
NFA는 State , 를 가지고
- 는 Accept State
가 된다. 인식하는 Language는
이다.
세 표현의 동등성
다음 세 조건은 동치이다.
이 동등성 덕분에 문제에 따라 가장 편리한 표현을 선택할 수 있다. Pattern은 RE가 간결하고, 실행은 DFA가 효율적이며, 문법적 생성은 Regular Grammar가 자연스럽다.
정리
- Right-linear Grammar는 Variable이 오른쪽 끝에 하나만 나타난다.
- Left-linear Grammar는 Variable이 왼쪽 끝에 하나만 나타난다.
- Regular Grammar와 Finite Automaton은 상호 변환할 수 있다.
- FA, RE, Regular Grammar는 같은 Regular Language Class를 표현한다.
연습 문제
1번
다음 Grammar를 NFA로 변환하고 Language를 설명한다.
2번
DFA에 State , 이 있고 에서 0은 , 1은 , 에서 0과 1은 로 이동한다. 이 Accept State일 때 Right-linear Grammar를 작성한다.
풀이
1번
State , 를 만들고 를 Accept State로 둔다. Transition은 , , 이다. Language는
이다.
2번
로 둘 수 있다.