이산수학: 형식 언어와 문법

언어 세 가지 요소로 구성된다. 기호들의 집합 S가 반드시 존재한다 - 알파벳 S 로부터 문장들의 집합 S*를 형성하는 규칙이 반드시 존재한다. - Syntax 규칙에 합당하게 만들어진 문장들이 의미를 갖는지를 결정할 수 있어야 한다. - Semantics Syntax(문법) 문장의 적합한 구성에 대한 규정 Semantics(의미론) 문장의 적합한 의미에 대한 규정 형식 언어 심벌 : 기호 알파벳 : 기호들의 유한 집합(V) 문자열 : 알파벳에 포함된 기호들이 나열된 것(V*) 공 문자열 : 길이가 0인 문자열, λ로 표시 (공집합 과는 다르다.) 구 - 구문 문법 V : 기호의 집합 = 비 단말 기호 T : 단말 기호 S : 시작 기호 P : 생성 규칙 (=>로 표시) 언어와 문법 문법 G의 언어 문법 G를 사용하여 만들어 질 수 있는 문장들의 집합 문법의 종류 유형 0 문법(비 제한 문법) 생성에 아무 제약이 없다. 유형 1 문법(문맥 의존 문법: context sensitive...

원문링크 : 이산수학: 형식 언어와 문법