cfpq_data.grammars.converters.cnf

Create a context-free grammar in Chomsky normal form from different formats.

Functions

cnf_from_cfg(cfg)	Create a context-free grammar in Chomsky normal form [1] from given context-free grammar [2].
cnf_from_regex(regex)	Create a context-free grammar in Chomsky normal form [1] from given regular expression [2].
cnf_from_rsa(rsa)	Create a context-free grammar in Chomsky normal form [1] from Recursive State Automaton [2].

cnf_from_cfg(cfg: CFG) → CFG

Create a context-free grammar in Chomsky normal form [1] from given context-free grammar [2].

Parameters:

cfg (CFG) -- Context-free grammar.

Examples

>>> from cfpq_data import *
>>> gr = cfg_from_text("S -> a b")
>>> cnf = cfpq_data.cnf_from_cfg(gr)
>>> cfg_to_text(cnf)
'S -> a#CNF# b#CNF#\na#CNF# -> a\nb#CNF# -> b'

Returns:

cnf -- Context-free grammar in Chomsky normal form.

Return type:

CFG

References

[1] (1,2)

https://en.wikipedia.org/wiki/Chomsky_normal_form

[2] (1,2)

https://en.wikipedia.org/wiki/Context-free_grammar#Formal_definitions

cnf_from_regex(regex: Regex) → CFG

Create a context-free grammar in Chomsky normal form [1] from given regular expression [2].

Parameters:

regex (Regex) -- Regular expression.

Examples

>>> from cfpq_data import *
>>> expr = regex_from_text("a*")
>>> cnf = cfpq_data.cnf_from_regex(expr)
>>> cfg_to_text(cnf)
'S -> \nS -> S S\nS -> a'

Returns:

cnf -- Context-free grammar in Chomsky normal form.

Return type:

CFG

References

[1] (1,2)

https://en.wikipedia.org/wiki/Chomsky_normal_form

[2] (1,2)

https://en.wikipedia.org/wiki/Regular_expression#Formal_definition

cnf_from_rsa(rsa: RecursiveAutomaton) → CFG

Create a context-free grammar in Chomsky normal form [1] from Recursive State Automaton [2].

Parameters:

rsa (RSA) -- Recursive State Automaton.

Examples

>>> from cfpq_data import *
>>> gr = rsa_from_text("S -> a*")
>>> cnf = cnf_from_rsa(gr)
>>> cfg_to_text(cnf)
'S -> \nS -> a\nS -> a#CNF# S\na#CNF# -> a'

Returns:

cnf -- Context-free grammar in Chomsky normal form.

Return type:

CFG

References

[1] (1,2)

https://en.wikipedia.org/wiki/Chomsky_normal_form

[2] (1,2)

Alur R., Etessami K., Yannakakis M. (2001) Analysis of Recursive State Machines. In: Berry G., Comon H., Finkel A. (eds) Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science, vol 2102. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44585-4_18