Writing in Chomsky Normal Form $($CNF$)$

You will be asked to write grammars for CFL$\text{'}$s$.$ The grammar must be in Chomsky Normal Form $($CNF$).$ Review carefully the description of CNF from the textbook, Definition $2\mathrm{.}8.$

Writing in CNF is tricky, so first write your grammar without worrying about CNF$,$ and then convert it to CNF$.$ The book has a proceedure for doing this, but it might be easier to do it taking ideas from the conversion procedure, but not following it strictly.

The dictionary for the grammar has a set for terminals, a set for variables, a set for rules and a slot for the start vaiable. Terminals must be single characters, lower case letters or digits. The Variables must start with an uppercase letter, and can be more than one character, but the following characters must be lowercase letters or a digits. The rules diction as variables as keys and a list of strings as values. Note that there are no spaces in the rules.

Note that all variables must be listed in the variables property or else the object parsing the grammar will assert and error. As a reminder, the variable given as start cannot appear on the right hand side of a rule, and is the only variable allowed to have the empty string on the right hand side of a rule.

The empty string is given as $"".$

I give an example for the language $($ab$)*$:

cfg$\_$ab$\_$star $=\{$

'terminals':$\{\text{'}$a$\text{'},\text{'}$b$\text{'}\},$

'variables':$\{\text{'}$S$\text{'},\text{'}$Va$\text{'},\text{'}$Vb$\text{'},\text{'}$T$\text{'}\},$

'start':$\text{'}$S$\text{'},$

'rules':$\{$

$\text{'}$S$\text{'}$:$[\text{'}\text{'},$'VaVb',$\text{'}$TT$\text{'}],$

$\text{'}$T$\text{'}$:$[\text{'}$TT$\text{'},$'VaVb'$],$

$\text{'}$Va$\text{'}$:$[\text{'}$a$\text{'}],$

$\text{'}$Vb$\text{'}$:$[\text{'}$b$\text{'}]$

$\}$

$\}$

from cyk$\_$solver import $*$

assert$\_$honor$\_$code$()$

lang$\_$ab$\_$star $=[[\text{'}\text{'},\text{'}$ab$\text{'},$'abab','abababab'$],$ # positive examples

$[\text{'}$a$\text{'},\text{'}$b$\text{'},\text{'}$ba$\text{'},$'aba','bab'$]]$ # negative examples

test$\_$cyk$($cfg$\_$ab$\_$star,lang$\_$ab$\_$star$)$

OK: correct accepts $||$

OK: correct accepts $|$ab$|$

OK: correct accepts $|$abab$|$

OK: correct accepts $|$abababab$|$

OK: correctly rejects $|$a$|$

OK: correctly rejects $|$b$|$

OK: correctly rejects $|$ba$|$

OK: correctly rejects $|$aba$|$

OK: correctly rejects $|$bab$|$

PASS: all $9$ tests correct.

Excercise B

How about strings over a$,$ b of the form a$^$i b$^$j where $2$i$=3$j

How about strings over a$,$ b where the number of a$\text{'}$s is twice the number of b$\text{'}$s$.$

# a$^$i b$^$j where $2$i$=3$j

cfg$\_2$i$3$j $=\{$

'terminals':$\{\text{'}$a$\text{'},\text{'}$b$\text{'}\},$

'variables':$\{\text{'}$S$\text{'},\text{'}$Va$\text{'},\text{'}$Vb$\text{'},\text{'}$T$\text{'}\},$

'start':$\text{'}$S$\text{'},$

'rules':$\{$

$\text{'}$S$\text{'}$:$[\text{'}\text{'},$'VaVb',$\text{'}$TT$\text{'}],$

$\text{'}$T$\text{'}$:$[\text{'}$TT$\text{'},$'VaVb'$],$

$\text{'}$Va$\text{'}$:$[\text{'}$a$\text{'}],$

$\text{'}$Vb$\text{'}$:$[\text{'}$b$\text{'}]$

$\}$

$\}$

$$

# strings in a and b where there are twice the number of a$\text{'}$s than b$\text{'}$s$.$

$$

cfg$\_$b$2$a $=\{$

'terminals':$\{\text{'}$a$\text{'},\text{'}$b$\text{'}\},$

'variables':$\{\text{'}$S$\text{'},\text{'}$Va$\text{'},\text{'}$Vb$\text{'},\text{'}$T$\text{'}\},$

'start':$\text{'}$S$\text{'},$

'rules':$\{$

$\text{'}$S$\text{'}$:$[\text{'}\text{'},$'VaVb',$\text{'}$TT$\text{'}],$

$\text{'}$T$\text{'}$:$[\text{'}$TT$\text{'},$'VaVb'$],$

$\text{'}$Va$\text{'}$:$[\text{'}$a$\text{'}],$

$\text{'}$Vb$\text{'}$:$[\text{'}$b$\text{'}]$

$\}$

$\}$

$$

#

# sanity check

#

assert$\_$honor$\_$code$()$

$$

lang$\_2$i$3$j$\_$test $=[[\text{'}$aaabb$\text{'},$'aaaaaabbbb','aaaaaabbbb'$],$ # positive examples

$[\text{'}$ab$\text{'},$'bbaaa','ababab'$]]$ # negative examples

result$\_$summary$[\text{'}2$i$3$j$\text{'}]=$ test$\_$cyk$($cfg$\_2$i$3$j$,$lang$\_2$i$3$j$\_$test$)$

$$

lang$\_$b$2$a$\_$test $=[[\text{'}$baa$\text{'},$'aba','baa','bbaaaa','baabaa','babaaa'$],$ #posigive examples

$[\text{'}$a$\text{'},\text{'}$b$\text{'},\text{'}$aa$\text{'},\text{'}$bb$\text{'},$'babaaaa','baaba'$]]$ # negative examples

result$\_$summary$[\text{'}$b$2$a$\text{'}]=$ test$\_$cyk$($cfg$\_$b$2$a$,$lang$\_$b$2$a$\_$test$)$