Theory: Is the grammar in Chomsky normal form?

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 CNF if 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")

Lesson: Parsing with the CYK algorithm →