Check the condition CYK needs before parsing.
What to build
A program that checks whether every rule of a grammar is in Chomsky normal form.
Requirements
- Print
CNFif every rule is A → BC or A → a. - Otherwise print
not CNF:followed by the first rule that is not.
Input
Line 1: r. Then r lines A -> body, one body per line. Capital letters are variables; anything else is a terminal.
Output
One line.
Constraints
r ≤ 20; bodies have at most 6 symbols.
Example
Input:
3
S -> AB
A -> a
B -> b
Output:
CNF
Why it works
CYK splits a substring into exactly two parts or matches one terminal, which works only when every rule has one of those two shapes.
Examples
Example 1 · Input
3 S -> AB A -> a B -> b
Expected output
CNF
Example 2 · Input
2 S -> aB B -> b
Expected output
not CNF: S -> aB
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A body is fine if it is two capital letters, or one lowercase letter or symbol that is not a capital.
Hint 2
Check the rules in order and stop at the first bad one.
Solution
Show one correct solution (try it yourself first)
rules = [input().strip() for _ in range(int(input()))]
def ok(body):
if len(body) == 2:
return body[0].isupper() and body[1].isupper()
return len(body) == 1 and not body.isupper()
for rule in rules:
head, body = rule.split(" -> ")
if not ok(body):
print("not CNF:", rule)
break
else:
print("CNF")