문맥자유문법,context-free_grammar,CFG

pagename 문맥무관문법 이 좋지 않을지? context-free vs context-sensitive (저기에 해당하는 문법인 CSG는 문맥민감문법? wpko는 WpKo:문맥_의존_문법) 둘이 서로 compl. 같은데.. chk
//하텍 02주 1강 p8:
정의
CFG G는 네 구성요소 V, T, S, P로 이루어진 수학적 구조이며
  • V : nonterminal이라 부르는 symbol들의 유한 집합
  • T : terminal이라 부르는 symbol들의 유한집합이고 V ∩ T = ∅
  • S : 시작하는 nonterminal이고 S ∈ V
  • P : 생성규칙,production_rule들의 유한집합으로, 생성규칙은 x → y 형식으로 표현되는데 여기서
    x ∈ V 이고,
    y는 V ∪ T 안에 있는 원소들을 연결시켜 만들 수 있는 문자열,string
//p9:
nonterminal : 변수와 비슷, 고정되지 않음, 여러 가지 값을 가질 수 있는 symbol
terminal : 상수와 비슷, 고정된 것

nonterminal은 terminal 중 하나의 값으로 치환될 수 있다.

CFG로 만들어진/생성된 언어,language : 문맥자유언어,context-free_language,CFL ? chk


rel. CFG를 parsing하는 algorithm: CYK알고리듬,CYK_algorithm(writing)

모든 생성규칙,production_rule이 .......의 형태를 가지면 .....tbw




문맥자유문법 context-free grammar CFG AKA 문맥무관문법
Up: 형식문법,formal_grammar