문법과 언어

문법과 언어의 관계는 문법이 존재하면 언어를 생성할 수 있고, 언어가 만들어지기 위해서는 문법을 고안해야 한다.

문법은 4 가지로 구성요소로 이루어진다.

G=(V_N , V_T , P , S)

• V_N 는 non-terminal 심벌의 집합
• V_T 는 terminal 심벌의 집합
• P 는 유도 규칙
• S 는 시작 심벌

Non-terminal 이란 '확장할 수 있다'라는 의미이고 , terminal 이란 '확장할 수 없다'는 의미이다. Non-terminal 심벌은 이 심벌에서 계속 확장 할수 있다는 의미이고 , terminal 심벌은 이 심벌로는 더 이상 확장할 수 없는 종착 심벌이란 의미이다.

Non-terminal 기호는 관례상 대문자로 사용하고 , terminal 기호는 소문자를 사용한다.

(보기) 아래 보기와 같은 문법이 정의될 때 이 문법이 생성하는 언어를 구하는 문제이다.

G=( {S,C},{a,b},P,S)

P:   S -> aCa
     C -> aCa | b

(풀이) 시작심벌이 S 이므로 S 에서 유도할 수 있는 규칙은

a 는 더 이상 유도할 수 없는 터미널 심벌이고 , C 는 aCa 혹은 b 로 유도될 수 있고

• C -> b 로 유도된다면 aba 스트링을 만들수 있고

  

• C -> aCa 로 유도된다면

  

• C -> b 로 유도된다면 aabaa 스트링을 만들수 있고

  

이 과정을 계속한다면, 이 문법이 만들수 있는 스트링은 b 양쪽에 a 가 같은 개수만큼 올수 있는 스트링을 만들수 있다.

즉 이 문법으로 만들 수 있는 언어는

L(G)= { aⁿ · b · aⁿ | n >= 1 }

###

(유제) 다음과 같은 문법이 주어질 때 이 문법으로 생성할 수 있는 언어를 구하는 문제이다.

G={ {O,E} , {a} , P, O}

P: O -> a |aE 

   E -> aO