촘스키 정규형 문법

문맥 자유 문법이 촘스키 정규형(CNF)으로 주어진다. 이 문법은 다음으로 이루어진다.

• 비단말 기호의 집합 $N$
• 단말 기호의 집합 $T$
• $N$에 속하는 시작 기호 $S$
• $A \to BC$ 또는 $A \to a$ 꼴의 규칙 집합 $R$ ($A, B, C \in N$, $a \in T$)

$A \in N$에 대해 $A$가 생성하는 언어 $L(A)$를 다음과 같이 정의한다.

$L(A) = \{\,wz \mid w \in L(B),\ z \in L(C),\ A \to BC \in R\,\} \cup \{\,a \mid A \to a \in R\,\}$

문법이 생성하는 언어는 시작 기호의 언어 $L(S)$이다. 문자열 $x$가 주어지면 $x$가 $L(S)$에 속하는지 판정하라.

첫째 줄에 문자열 $x$가 주어진다. $x$는 알파벳 소문자로만 이루어지고 길이는 1 이상 1000 이하이다.

둘째 줄부터 파일의 끝까지 문법 규칙이 한 줄에 하나씩 주어진다. 비단말 기호는 알파벳 대문자로, 단말 기호는 알파벳 소문자로 쓴다. 길이가 3인 줄 ABC는 규칙 $A \to BC$를 뜻하고 길이가 2인 줄 Aa는 규칙 $A \to a$를 뜻한다. 시작 기호는 항상 S이다. 규칙은 한 개 이상 주어지며 같은 규칙이 두 번 이상 나올 수 있다.

$x$가 문법이 생성하는 언어에 속하면 1을, 속하지 않으면 0을 한 줄에 출력한다.