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:

cfgCFG: Context-free grammar.
mapping: Dict[str, str]: Terminals mapping.

Returns:

cfgCFG: Context-free grammar with changed terminals.

References

[1] (1,2)

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

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'

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:

cnfCFG: Context-free grammar in Chomsky normal form.
mapping: Dict[str, str]: Terminals mapping.

Returns:

cnfCFG: Context-free grammar in Chomsky normal form with changed terminals.

References

[1] (1,2)

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

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#'

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

Change terminals of a regular expression [1].

Parameters:

regexRegex: Regular expression.
mapping: Dict[str, str]: Terminals mapping.

Returns:

regexRegex: Regular expression with changed terminals.

References

[1] (1,2)

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

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)*))'

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

Change terminals of a Recursive State Automaton [1].

Parameters:

rsaRSA: Recursive State Automaton.
mapping: Dict: Terminals mapping.

Returns:

rsaRSA: Recursive State Automaton with changed terminals.

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

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)*'