Grammar의 정의와 Regular Grammar

 

 

 

0. Chompsky Hierchy

 

Grammar, 즉 문법이라고 함은(평소에 우리가 쓰는 단어) 어떤 언어에 대해서 정해져 있는 규칙들을 모아 문법이라고 칭합니다.

그렇다면 regular grammar, 특히 계산이론에서의 regular grammar는 컴퓨터 언어에 있어서의 문법을 이야기합니다.

특히 컴퓨터 언어에서의 grammar를 제안한 사람은 바로 Noam Chompsky입니다. 총 4가지의 grammar를 제시했는데, 보도록 합시다.

 

Grammar Type	Grammar Accepted	Language Accepted	Automaton
TYPE-0	Unrestricted Grammar	Recursively Enumerable Language	Turing Machine
TYPE-1	Context Sensitive Grammar	Context Sensitive Language	Linear Bounded Automaton
TYPE-2	Context Free Grammar	Context Free Language	Pushdown Automata
TYPE-3	Regular Grammar	Regular Language	Finite State Automaton

 

네, 다음과 같이 4가지 문법을 제시하였고, 아마 순서대로 공부하시면서 Regular Grammar까지 왔다면 TYPE-3의 Regular Language까지밖에 배우지 않았을 겁니다.

단순히 관계성을 보이기 위해 인용한거라 TYPE-0~2까지는 몰라도 상관없습니다.

 

이 표를 보고 파악해야할 점은 단순히 "Automaton"은 언어의 시각화/구현 모델, "Language Accepted"는 해당되는 언어의 형식, 그리고 "Grammar Accepted"는 이 언어의 규칙을 나타낸 것이라고 보면 됩니다.

그리고 이 Type들은 포괄하는 정도에 따라 나눈 것이라고 보면 됩니다.

대략적인 느낌만 잡으면 됩니다. 

 

1. Grammar

그러면 공식적인 정의를 한번만 보고 갑시다.

Grammar G can be defined with 4 tuples as G = (V,T,S,P).

 

V = Set of Variables or Non-Terminal Symbols

T = Set of Terminal Symbols

S = Start Symbols

P = Production rules for Terminal and Non-Terminals

 

다음과 같은데 어차피 직접 예시로 봐야 조금 느낌이 오니깐 예시를 보도록 하겠습니다.

example

예시를 보면 알 수 있겠지만, Language랑 비슷하다는 느낌이 듭니다. 굳이 풀어서 썼다정도의 느낌인 것 같아요.

근데 당연히 규칙을 쓴 것이니, 당연한 것이겠죠?

아 Grammar란 이런거구나만 들고 가도록 합시다.

 

 

2. Regular Grammar

Regular Grammar는 Grammar들 중 Right Linear Grammar이거나, Left Linear Grammar인 문법을 Regular Grammar라고 합니다.

 

그렇다면 Right/Left Linear Grammar가 무엇이냐?

앞서 이야기한 Grammar에서 P, 즉 Production을 보고 판단합니다.

 

다음 부분이 각각 Right-Linear와 Left-Linear Grammar에 대한 설명입니다. 아무튼 문법을 작성할 때, 그 production이 한쪽으로만 추가가 되면 Linear Grammar라고 하게 되고, Right과 Left는 Non-terminal symbols, 이 예시에서는 C를 보고 판단합니다.

 

 

3. Grammar에서 Language 뽑아내기

 

자 Grammar는 Language의 규칙을 정리한 것을 grammar라고 하기로 했습니다. 그렇다면 상식적으로 생각해보았을 때, 당연히 Grammar를 통해서 Language를 구하는 것도 가능하겠죠?

 

1) 전수조사

당연히 가장 쉽고 단순한 방법은 노가다입니다. 계속해서 케이스를 만들어내고, 그 사이에서 language를 뽑아내는 방법입니다.

 

 

2) 편법? 경험 기반으로 찾아낸 방법

 

뭐 당연히 다 쓰면 나오니깐 좋긴한데, 몇가지만 확인해도 충분히 language를 구할 수 있어서 정리해봅니다.

이건 그냥 제 경험기반이라 틀릴수도 있으니, 쓰신다고해도 참고만 하시길 바랍니다.

 

일단 우선적으로 확인해야할 것은 terminal symbols끼리 종속적인지, 독립적인지 확인해야 합니다. 

위의 경우에는 A -> aA|a 의 형식으로 되어있기 때문에, A는 결론적으로 임의의 갯수의 a를 뜻하고, b도 임의의 갯수의 b를 뜻합니다. 

결론부터 이야기하자면 이 케이스에서 A와 B는 독립적입니다. 왜냐하면 Production Rule에 A와 B가 혼합되어 발생하지 않기 때문이죠. 만약 Production rule이 A -> aA|a가 아니라 A -> aAb|a 이런 식이였다면 language는 다르게 쓰여졌겠죠?

 

그리고 또 항상 확인해줘야하는게 새로 쓰는 변수들의 범위는 항상 명시해야합니다.

예를 들어 위 예시는 L(G₃) = {a^mbⁿ | m>=0 and n>=0}인데, 여기서 m와 n의 범위를 꼭 명확히 표현해야한다는 것입니다.

되게 당연한거고 풀기전에는 에이~그걸 어케 까먹어ㅎ 하는데 막상 까먹을때가 엄청 많더라구요. 

그리고 단순히 양수냐 음수냐를 떠나서, 변수들간의 대소관계 또한 꼭 확인을 해야합니다.

 

그나마 의식적으로 이정도만 확인해도 실수가 많이 줄더라고요.

오늘은 여기서 끝!