Preview CFG: Many axb

  • Grammar:
    • 1 production per line
    • start nonterminal: left-hand side of first production
    • Remove: Right click on state ➞ 'Remove'
  • Productions:
    • form: S -> X Y | a S b | \eps
    • left-hand side: a single nonterminal
    • right-hand side: groups of nonterminals and terminals separated by "|"
  • Nonterminals:
    • form: one single upper case character A-Z
  • Terminals:
    • allowed: abcdefghijklmnopqrstuvwxyz()[]{}
  • Empty word::
    • empty word: ε (write \epsilon or \eps or \e)

Problem

For the grammar with the productions:

S → C B | x | S S
C → A S
A → a
B → b

Perform the CYK algorithm!

(For each cell: List the corresponding non-terminals separated by a whitespace.)

(1,5)
(1,4) (2,5)
(1,3) (2,4) (3,5)
(1,2) (2,3) (3,4) (4,5)
(1,1) (2,2) (3,3) (4,4) (5,5)
'a' 'b' 'a' 'x' 'b'