4 - Formal Language Grammer

Formal Language는 4가지 구성요소로 이루어져 있다.

 

 

구성요소

Vn - 생성 규칙을 나타내며 알파벳 대문자로 나타낸다.

Vt - 실제로 나타내는 string을 나타내며 알파벳 소문자로 나타낸다.

P - 생성 규칙 전체를 말한다.

S - Starting Symbol, 시작을 나타낸다.

 

예제

1)

P :
	S -> aA    
    A -> 1
    A -> k
    A -> _3

 

a(Vt) 는 실제로 나타내는 언어이기 때문에 그대로 둔다.

A(Vn)은 생성 규칙으로 1이나 k, _3으로 치환될 수 있다.

즉 S는 a1, ak, a_3이 될 수 있다.

A에 관한 식들은 A -> 1 | k | _3 으로도 표현이 가능하다.

 

2)

P:
	S -> aA | bB | ε
    A -> bS
    B -> aS

Vn = {S, A, B}

Vt = {a, b} ε은 포함하지 않음

이 표현식에서 abba 라는 형식이 유효한지 알아보자.

 

S -> aA -> abS -> abbB -> abbaS -> abbaε -> abba 

가능하다.

이런식으로 예를 들어 앞에 숫자가 오면 안되는 변수이름을 규칙으로 정하고 싶을 때 사용할 수 있다.