cfpq_data.grammars.utils.change_terminals#

Change terminals of a context-free grammar in different formats.

Functions

`change_terminals_in_cfg`(cfg, mapping)	Change terminals of a context-free grammar [1].
`change_terminals_in_cnf`(cnf, mapping)	Change terminals of a context-free grammar [1] in Chomsky normal form.
`change_terminals_in_regex`(regex, mapping)	Change terminals of a regular expression [1].
`change_terminals_in_rsa`(rsa, mapping)	Change terminals of a Recursive State Automaton [1].

change_terminals_in_cfg(cfg: CFG, mapping: Dict[str, str]) → CFG[source]#

Change terminals of a context-free grammar [1].

Parameters:

cfg (CFG) -- Context-free grammar.
mapping (Dict[str, str]) -- Terminals mapping.

Examples

>>> from cfpq_data import *
>>> cfg = cfg_from_text("S -> a S b S")
>>> new_cfg = change_terminals_in_cfg(cfg, {"a": "b", "b": "c"})
>>> cfg_to_text(new_cfg)
'S -> b S c S'

Returns:: cfg -- Context-free grammar with changed terminals.
Return type:: CFG

References

[1] (1,2)

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

change_terminals_in_cnf(cnf: CFG, mapping: Dict[str, str]) → CFG[source]#

Change terminals of a context-free grammar [1] in Chomsky normal form.

Parameters:

cnf (CFG) -- Context-free grammar in Chomsky normal form.
mapping (Dict[str, str]) -- Terminals mapping.

Examples

>>> from cfpq_data import *
>>> cnf = cnf_from_text("S -> a b")
>>> new_cnf = change_terminals_in_cnf(cnf, {"a": "b", "b": "c"})
>>> cfg_to_text(new_cnf)
'S -> b#CNF##CNF# c#CNF##CNF#\nb#CNF##CNF# -> b#CNF#\nc#CNF##CNF# -> c#CNF#'

Returns:: cnf -- Context-free grammar in Chomsky normal form with changed terminals.
Return type:: CFG

References

[1] (1,2)

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

change_terminals_in_regex(regex: Regex, mapping: Dict[str, str]) → Regex[source]#

Change terminals of a regular expression [1].

Parameters:

regex (Regex) -- Regular expression.
mapping (Dict[str, str]) -- Terminals mapping.

Examples

>>> from cfpq_data import *
>>> regex = regex_from_text("a (bc|d*)")
>>> new_regex = change_terminals_in_regex(regex, {"a": "b", "b": "c"})
>>> regex_to_text(new_regex)
'(b (cc|(d)*))'

Returns:: regex -- Regular expression with changed terminals.
Return type:: Regex

References

[1] (1,2)

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

change_terminals_in_rsa(rsa: RecursiveAutomaton, mapping: Dict[str, str]) → RecursiveAutomaton[source]#

Change terminals of a Recursive State Automaton [1].

Parameters:

rsa (RSA) -- Recursive State Automaton.
mapping (Dict) -- Terminals mapping.

Examples

>>> from cfpq_data import *
>>> rsa = rsa_from_text("S -> a*")
>>> new_rsa = change_terminals_in_rsa(rsa, {"a": "b"})
>>> rsa_to_text(new_rsa)
'S -> (b)*'

Returns:: rsa -- Recursive State Automaton with changed terminals.
Return type:: RSA

References

[1] (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