### Install Pyformlang from Local Sources

Source: https://pyformlang.readthedocs.io/en/latest/installation.html

After cloning the repository, use this command to install Pyformlang using its setup script. This method is for installing from downloaded source code.

```bash
python setup.py install

```

--------------------------------

### Install Pyformlang from Source

Source: https://pyformlang.readthedocs.io/en/latest/_sources/installation.rst.txt

Install Pyformlang after cloning the source code using the setup.py script.

```console
python setup.py install
```

--------------------------------

### Initialize CFG Productions from PDA Start State

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Initializes the list of CFG productions based on the PDA's start state and initial stack symbol. It generates productions for each possible state.

```python
def _initialize_production_from_start_in_to_cfg(self, start):
        productions = []
        for state in self._states:
            productions.append(
                cfg.Production(
                    start,
                    [self._cfg_variable_converter.to_cfg_combined_variable(
                        self._start_state,
                        self._start_stack_symbol,
                        state)]))
        return productions
```

--------------------------------

### Add Start State to DeterministicFiniteAutomaton

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Sets the start state for the DeterministicFiniteAutomaton. The state must be one of the automaton's defined states.

```python
>>> dfa.add_start_state(0)
```

--------------------------------

### Create Empty DeterministicFiniteAutomaton

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Initializes an empty DeterministicFiniteAutomaton. This is the starting point for building a DFA.

```python
>>> dfa = DeterministicFiniteAutomaton()
```

--------------------------------

### start_state

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Provides access to the start state of the deterministic finite automaton.

```APIDOC
## start_state

### Description
Gets the start state of the DFA.

### Property
`start_state`

### Returns
- `State`: The start state of the automaton.

### Examples
```python
dfa = DeterministicFiniteAutomaton()
dfa.add_start_state(0)
start = dfa.start_state
```
```

--------------------------------

### Set Start and Final States for DFA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Shows how to designate a start state and one or more final states for a DFA. These are crucial for defining the automaton's behavior and acceptance criteria.

```python
>>> dfa.add_start_state(0)
>>> dfa.add_final_state(1)
```

--------------------------------

### set_start_state Method

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Sets or updates the start state of the Pushdown Automaton.

```APIDOC
## set_start_state

### Description

Sets the start state for the automaton. If the provided state is not already in the set of states, it will be added.

### Parameters

- **start_state** (:class:`~pyformlang.pda.State`): The state to be set as the start state.
```

--------------------------------

### Initialize PDA

Source: https://pyformlang.readthedocs.io/en/latest/modules/push_down_automata.html

Initializes a Push-Down Automaton with optional states, input symbols, stack alphabet, transition function, start state, start stack symbol, and final states.

```python
PDA(_states : AbstractSet[Any] = None_, _input_symbols : AbstractSet[Any] = None_, _stack_alphabet : AbstractSet[Any] = None_, _transition_function : TransitionFunction = None_, _start_state : Any = None_, _start_stack_symbol : Any = None_, _final_states : AbstractSet[Any] = None_)
```

--------------------------------

### Add Start State to EpsilonNFA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/finite_automaton.html

Sets an initial state for the EpsilonNFA. Ensure the state exists before adding.

```python
>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1), \
(0, "epsilon", 2)])
>>> enfa.add_start_state(0)
```

--------------------------------

### Set Start State for PDA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Sets the start state for the push-down automaton. Ensures the provided state is converted to the internal State representation and added to the set of states.

```python
def set_start_state(self, start_state: Any):
        """ Sets the start state to the automaton

        Parameters
        ----------
        start_state : :class:`~pyformlang.pda.State`
            The start state
        """
        start_state = self._pda_obj_creator.to_state(start_state)
        self._states.add(start_state)
        self._start_state = start_state

```

--------------------------------

### Add and Remove Start State

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Demonstrates adding a new initial state and subsequently removing it from the DFA.

```python
dfa = DeterministicFiniteAutomaton()
dfa.add_start_state(0)
dfa.remove_start_state(0)
```

--------------------------------

### CFG Intersection Starting Rules Helper

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

A static helper method to generate the starting rules for the intersection of a CFG with another automaton. It creates new productions based on the start and final states of the other automaton.

```python
@staticmethod
def _intersection_starting_rules(cfg, other, cv_converter):
        start = Variable("Start")
        productions_temp = []
        start_other = list(other.start_states)[0]  # it is deterministic
        for final_state in other.final_states:
            new_body = [
                cv_converter.to_cfg_combined_variable(
                    start_other,
                    cfg.start_symbol,
                    final_state)]
            productions_temp.append(
                Production(start, new_body, filtering=False))
        return productions_temp
```

--------------------------------

### Initialize RecursiveAutomaton

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/rsa/recursive_automaton.html

Initializes a RecursiveAutomaton with a start box and a set of boxes. The start box's nonterminal is added to the mapping if it's not already present.

```python
from pyformlang.rsa.box import Box
from pyformlang.rsa.recursive_automaton import RecursiveAutomaton
from pyformlang.finite_automaton.finite_automaton import to_symbol

# Assuming Box and Symbol are defined elsewhere
# Example usage:
# start_box = Box(some_nfa, Symbol('A'))
# boxes = {start_box, Box(another_nfa, Symbol('B'))}
# rsa = RecursiveAutomaton(start_box, boxes)
```

--------------------------------

### Import PDA from NetworkX Graph

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Imports a PDA from a NetworkX graph. The graph must be in the format generated by `to_networkx`. This method reconstructs the PDA's states, transitions, start state, final states, and start stack symbol.

```python
pda = PDA()
for s_from in graph:
    if isinstance(s_from, str) and s_from.startswith("starting_"):
        continue
    for s_to in graph[s_from]:
        for transition in graph[s_from][s_to].values():
            if "label" in transition:
                in_symbol, stack_info = transition["label"].split(
                    " -> ")
                in_symbol = json.loads(in_symbol)
                stack_from, stack_to = stack_info.split(" / ")
                stack_from = json.loads(stack_from)
                stack_to = json.loads(stack_to)
                pda.add_transition(s_from,
                                   in_symbol,
                                   stack_from,
                                   s_to,
                                   stack_to)
for node in graph.nodes:
    if graph.nodes[node].get("is_start", False):
        pda.set_start_state(node)
    if graph.nodes[node].get("is_final", False):
        pda.add_final_state(node)
if "INITIAL_STACK_HIDDEN" in graph.nodes:
    pda.set_start_stack_symbol(
        json.loads(graph.nodes["INITIAL_STACK_HIDDEN"]["label"]))
return pda
```

--------------------------------

### add_start_state

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Sets an initial state for the DFA. If a start state already exists, it will be replaced.

```APIDOC
## add_start_state(state: Any)

### Description
Sets an initial state for the DFA. If a start state already exists, it will be replaced.

### Method
add_start_state

### Parameters
#### Path Parameters
- **state** (Any) - Required - The new initial state. Can be a State object or a value convertible to a State.

### Returns
- **done** (int) - Returns 1 upon successful addition of the start state.

### Request Example
```python
dfa = DeterministicFiniteAutomaton()
dfa.add_start_state(0)
```

### Response Example
```python
# Returns 1
```
```

--------------------------------

### Create and Configure EpsilonNFA

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Initializes an empty EpsilonNFA and adds transitions, a start state, and a final state. Checks if the automaton is deterministic.

```python
>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1), (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.is_deterministic()
False

```

--------------------------------

### start_symbol

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

Retrieves the start symbol (the main variable) of the CFG.

```APIDOC
## start_symbol

### Description
Gives the start symbol of the CFG.

### Method
```python
@property
def start_symbol(self) -> Variable:
    ...
```

### Returns
- **start_variable** (:class:`~pyformlang.cfg.Variable`): The start symbol of the CFG.
```

--------------------------------

### CFG Class Initialization

Source: https://pyformlang.readthedocs.io/en/latest/modules/context_free_grammar.html

Initializes a Context Free Grammar object with optional sets of variables, terminals, a start symbol, and productions.

```APIDOC
## CFG

### Description
A class representing a context free grammar.

### Parameters
- **variables** (set of `Variable` | `str`, optional) - The variables of the CFG.
- **terminals** (set of `Terminal` | `str`, optional) - The terminals of the CFG.
- **start_symbol** (`Variable` | `str`, optional) - The start symbol.
- **productions** (Iterable of `Production`, optional) - The productions or rules of the CFG.
```

--------------------------------

### Initialize NondeterministicTransitionFunction

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/nondeterministic_transition_function.html

Creates an empty nondeterministic transition function. Use this to start building transitions.

```python
transition = NondeterministicTransitionFunction()
```

--------------------------------

### Get Start Box

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/rsa/recursive_automaton.html

Returns the start Box object of the recursive automaton.

```python
@property
def start_box:
    """ The start box """

    return self.boxes[self.start_nonterminal]
```

--------------------------------

### Add states and transitions to NFA

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Demonstrates adding start and final states, as well as transitions to a Non-deterministic Finite Automaton (NFA).

```python
from pyformlang.finite_automaton import NFA, State, Symbol

state0 = State(0)
state1 = State(1)
state2 = State(2)
state3 = State(3)
state4 = State(4)
symb_a = Symbol("a")
symb_b = Symbol("b")
symb_c = Symbol("c")
symb_d = Symbol("d")

nfa = NFA()

# Add a start state
nfa.add_start_state(state0)
# Add a final state
nfa.add_final_state(state4)
nfa.add_final_state(state3)
# Add the transitions
nfa.add_transition(state0, symb_a, state1)
nfa.add_transition(state1, symb_b, state1)
nfa.add_transition(state1, symb_c, state2)
nfa.add_transition(state1, symb_d, state3)
nfa.add_transition(state1, symb_c, state4)
nfa.add_transition(state1, symb_b, state4)

# Check if a word is accepted
nfa.accepts([symb_a, symb_b, symb_c])

# Check if a NFA is deterministic
nfa.is_deterministic() # False

# Get the equivalent deterministic automaton
dfa = nfa.to_deterministic())
```

--------------------------------

### Get Start Nonterminal

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/rsa/recursive_automaton.html

Returns the start nonterminal Symbol of the recursive automaton.

```python
@property
def start_nonterminal(self) -> Symbol:
    """ The start nonterminal """

    return self._start_nonterminal
```

--------------------------------

### Get CFG Start Symbol

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

Retrieves the start symbol (the main variable) of the CFG.

```python
@property
def start_symbol(self) -> Variable:
        """ Gives the start symbol

        Returns
        ----------
        start_variable : :class:`~pyformlang.cfg.Variable`
            The start symbol of the CFG
        """
        return self._start_symbol
```

--------------------------------

### Create and Configure NFA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/nondeterministic_finite_automaton.html

Demonstrates how to create a new NondeterministicFiniteAutomaton, add transitions, set a start state, and add a final state. This is useful for defining simple NFAs programmatically.

```python
>>> nfa = NondeterministicFiniteAutomaton()
>>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)])
>>> nfa.add_start_state(0)
>>> nfa.add_final_state(1)
```

--------------------------------

### Python Regex Initialization Example

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/regular_expression/python_regex.html

Demonstrates how to initialize and use the PythonRegex class with a sample regular expression. It shows how to check if a string or a list of characters is accepted by the regex.

```python
>>> from pyformlang.regular_expression import PythonRegex

>>> p_regex = PythonRegex("a+[cd]")
>>> p_regex.accepts(["a", "a", "d"])
True

>>> p_regex.accepts("aad")
True
>>> p_regex.accepts(["d"])
False
```

--------------------------------

### Get FST Start States

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/fst/fst.html

Retrieves the set of start states for the FST. This property provides read-only access to the initial states.

```python
    @property
    def start_states(self):
        """ Get the start states of the FST

        Returns
        ----------
        start_states : set of any
            The start states of the FST
        """
        return self._start_states
```

--------------------------------

### Initialize DFA with Parameters

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Shows the initialization of a DeterministicFiniteAutomaton with explicit states, input symbols, transition function, start state, and final states.

```python
>>> dfa = DeterministicFiniteAutomaton(
...     states={State(0), State(1)},
...     input_symbols={Symbol("a"), Symbol("b")},
...     transition_function=TransitionFunction({(State(0), Symbol("a")): State(1)}),
...     start_state=State(0),
...     final_states={State(1)}
... )
```

--------------------------------

### Get Reachable States

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/finite_automaton.html

Calculates and returns all states that are reachable from the start states of the automaton. This is fundamental for state space exploration.

```python
def _get_reachable_states(self) -> Set[State]:
        """ Get all states which are reachable """
        visited = set()
        states_to_process = deque(self.start_states)
        while states_to_process:
            current_state = states_to_process.popleft()
            visited.add(current_state)
            for next_state in self._get_next_states_from(current_state):
                if next_state not in visited:
                    states_to_process.append(next_state)
        return visited
```

--------------------------------

### Create and Minimize DFA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Demonstrates the creation of a DFA, adding transitions, start and final states, and then minimizing it. It also shows how to check for equivalence between the original and minimized DFA.

```python
dfa = DeterministicFiniteAutomaton()
dfa.add_transitions([(0, "abc", 1), (0, "d", 1)])
dfa.add_start_state(0)
dfa.add_final_state(1)
dfa_minimal = dfa.minimize()
dfa.is_equivalent_to(dfa_minimal)
```

--------------------------------

### Create Context-Free Grammar with Explicit Components

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Demonstrates the creation of a CFG using explicit Variable, Terminal, and Production objects, including epsilon productions.

```python
from pyformlang.cfg import Production, Variable, Terminal, CFG, Epsilon

# Creation of variables
var_useless = Variable("USELESS")
var_S = Variable("S")
var_B = Variable("B")

# Creation of terminals
ter_a = Terminal("a")
ter_b = Terminal("b")
ter_c = Terminal("c")

# Creation of productions
p0 = Production(var_S, [ter_a, var_S, var_B])
p1 = Production(var_useless, [ter_a, var_S, var_B])
p2 = Production(var_S, [var_useless])
p4 = Production(var_B, [ter_b])
p5 = Production(var_useless, [])

# Creation of the CFG
cfg = CFG({var_useless, var_S}, {ter_a, ter_b}, var_S, {p0, p1, p2, p4, p5})

# Check for containment
cfg.contains([Epsilon()])
cfg.contains([ter_a, ter_b])
```

--------------------------------

### Getting Reachable Non-terminals

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/indexed_grammar/indexed_grammar.html

Identifies all non-terminal symbols that are reachable from the start variable in an indexed grammar. It uses a breadth-first search approach.

```python
# Preprocess
reachable_from = {}
consumption_rules = self.rules.consumption_rules
for rule in self.rules.rules:
    if rule.is_duplication():
        left = rule.left_term
        right0 = rule.right_terms[0]
        right1 = rule.right_terms[1]
        if left not in reachable_from:
            reachable_from[left] = set()
        reachable_from[left].add(right0)
        reachable_from[left].add(right1)
    if rule.is_production():
        left = rule.left_term
        right = rule.right_term
        if left not in reachable_from:
            reachable_from[left] = set()
        reachable_from[left].add(right)
for key in consumption_rules:
    for rule in consumption_rules[key]:
        left = rule.left_term
        right = rule.right
        if left not in reachable_from:
            reachable_from[left] = set()
        reachable_from[left].add(right)
# Processing
to_process = [self.start_variable]
reachables = {self.start_variable}
while to_process:
    current = to_process.pop()
    for symbol in reachable_from.get(current, []):
        if symbol not in reachables:
            reachables.add(symbol)
            to_process.append(symbol)
return reachables
```

--------------------------------

### Get Reachable Symbols in CFG

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

Identifies all symbols in a CFG that are reachable from the start symbol. This is useful for simplifying grammars by removing unreachable parts.

```python
r_symbols = set()
        r_symbols.add(self._start_symbol)
        reachable_transition_d = {}
        for production in self._productions:
            temp = reachable_transition_d.setdefault(production.head, [])
            for symbol in production.body:
                if not isinstance(symbol, Epsilon):
                    temp.append(symbol)
        to_process = [self._start_symbol]
        while to_process:
            current = to_process.pop()
            for next_symbol in reachable_transition_d.get(current, []):
                if next_symbol not in r_symbols:
                    r_symbols.add(next_symbol)
                    to_process.append(next_symbol)
        return r_symbols
```

--------------------------------

### Create and Analyze Context-Free Grammar from Text

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Shows how to create a CFG from a string representation and perform operations like intersection, emptiness check, and containment checks.

```python
from pyformlang.cfg import CFG
from pyformlang.cfg.llone_parser import LLOneParser
from pyformlang.regular_expression import Regex

cfg = CFG.from_text("""
    S -> NP VP PUNC
    PUNC -> . | !
    VP -> V NP
    V -> buys | touches | sees
    NP -> georges | jacques | leo | Det N
    Det -> a | an | the
    N -> gorilla | dog | carrots""")
regex = Regex("georges touches (a|an) (dog|gorilla) !")

cfg_inter = cfg.intersection(regex)
cfg_inter.is_empty()  # False
cfg_inter.is_finite()  # True
cfg_inter.contains(["georges", "sees",
                    "a", "gorilla", "."])  # False
cfg_inter.contains(["georges", "touches",
                    "a", "gorilla", "!"])  # True

cfg_inter.is_normal_form()  # False
cnf = cfg.to_normal_form()
cnf.is_normal_form()  # True

llone_parser = LLOneParser(cfg)
parse_tree = llone_parser.get_llone_parse_tree(
    ["georges", "sees", "a", "gorilla", "."])
parse_tree.get_leftmost_derivation()
# [[Variable("S")],
#  [Variable("NP"), Variable("VP"), Variable("PUNC")],
#  ...,
#  [Terminal("georges"), Terminal("sees"),
#   Terminal("a"), Terminal("gorilla"), Terminal(".")]]
```

--------------------------------

### Get Accepted Words from EpsilonNFA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/finite_automaton.html

Provides an example of retrieving all words accepted by an EpsilonNFA up to a specified maximum length. This is useful for understanding the language recognized by the automaton.

```python
if max_length is not None and max_length < 0:
    return []
states_to_visit = deque((start_state, [])
                            for start_state in self.start_states)
states_leading_to_final = self._get_states_leading_to_final()
words_by_state = {state: set() for state in self.states}
yielded_words = set()
while states_to_visit:
    current_state, current_word = states_to_visit.popleft()
    if max_length is not None and len(current_word) > max_length:
        continue
    word_to_add = tuple(current_word)
    if not self.__try_add(words_by_state[current_state], word_to_add):
        continue
    transitions = self._transition_function.get_transitions_from(
        current_state)
    for symbol, next_state in transitions:
        if next_state in states_leading_to_final:
            temp_word = current_word.copy()
            if symbol != Epsilon():
                temp_word.append(symbol)
            states_to_visit.append((next_state, temp_word))
    if self.is_final_state(current_state):
        if self.__try_add(yielded_words, word_to_add):
            yield current_word
```

--------------------------------

### Create and Use a Deterministic Finite Automaton (DFA)

Source: https://pyformlang.readthedocs.io/en/latest/usage.html

This snippet demonstrates how to create a DFA by adding states, symbols, start state, final states, and transitions. It also shows how to check if a given word is accepted by the DFA.

```python
from pyformlang.finite_automaton import DeterministicFiniteAutomaton
from pyformlang.finite_automaton import State
from pyformlang.finite_automaton import Symbol

# Declaration of the DFA
dfa = DeterministicFiniteAutomaton()

# Creation of the states
state0 = State(0)
state1 = State(1)
state2 = State(2)
state3 = State(3)

# Creation of the symbols
symb_a = Symbol("a")
symb_b = Symbol("b")
symb_c = Symbol("c")
symb_d = Symbol("d")

# Add a start state
dfa.add_start_state(state0)

# Add two final states
dfa.add_final_state(state2)
dfa.add_final_state(state3)

# Create transitions
dfa.add_transition(state0, symb_a, state1)
dfa.add_transition(state1, symb_b, state1)
dfa.add_transition(state1, symb_c, state2)
dfa.add_transition(state1, symb_d, state3)

# Check if a word is accepted
dfa.accepts([symb_a, symb_b, symb_c])

```

--------------------------------

### Create and Configure a Push-Down Automata

Source: https://pyformlang.readthedocs.io/en/latest/usage.html

This snippet demonstrates how to explicitly declare states, symbols, and stack symbols to create a PDA. It also shows how to add transitions and transform the PDA to accept by empty stack or by final state.

```python
from pyformlang.pda import PDA, State, StackSymbol, Symbol, Epsilon

# Declare states
q = State("#STARTTOFINAL#")
q0 = State("q0")

# Declare symbols
e = Symbol("e")
i = Symbol("i")

# Declare stack symbols
Z = StackSymbol("Z")
Z0 = StackSymbol("Z0")

# Create the PDA
pda = PDA(states={q, q0},
          input_symbols={i, e},
          stack_alphabet={Z, Z0},
          start_state=q,
          start_stack_symbol=Z0,
          final_states={q0})

# Add transitions
pda.add_transition(q, i, Z, q, (Z, Z))
pda.add_transition(q, i, Z0, q, (Z, Z0))
pda.add_transition(q, e, Z, q, [])
pda.add_transition(q, Epsilon(), Z0, q0, [])

# Transformation to a PDA accepting by empty stack
pda_empty_stack = pda.to_empty_stack()
# Transformation to a PDA accepting by final state
pda_final_state = pda_empty_stack.to_final_state()
```

--------------------------------

### Get Regex for Simple Automaton

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/epsilon_nfa.html

Internal method to derive the regular expression of an automaton composed solely of a start and a final state. Raises a ValueError if the automaton is not simple enough. This method is intended for internal use only.

```python
def _get_regex_simple(self) -> str:
    """ Get the regex of an automaton when it only composed of a start and
    a final state

    CAUTION: For internal use only!

    Returns
    ----------
    regex : str
        A regex representing the automaton
    """
    if not self._final_states or not self._start_state:
        return ""
    if len(self._final_states) != 1 or len(self._start_state) != 1:
        raise ValueError("The automaton is not simple enough!")
    if self._start_state == self._final_states:
        # We are suppose to have only one good symbol
        for symbol in self._input_symbols:
            out_states = self._transition_function(
                list(self._start_state)[0], symbol)
            if out_states:
                return "(" + str(symbol.value) + ")*"
        return "epsilon"
    start_to_start, start_to_end, end_to_start, end_to_end = \
        self._get_bi_transitions()
    return get_regex_sub(start_to_start,
                         start_to_end,
                         end_to_start,
                         end_to_end)
```

--------------------------------

### Add Start State to FST

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/fst/fst.html

Adds a start state to the FST. This method ensures the state is added to both the set of all states and the set of start states.

```python
    def add_start_state(self, start_state: Any):
        """ Add a start state

        Parameters
        ----------
        start_state : any
            The start state
        """
        self._states.add(start_state)
        self._start_states.add(start_state)
```

--------------------------------

### Converting CFG to PDA and back

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Shows the conversion process between a Context-Free Grammar (CFG) and a Pushdown Automaton (PDA). It demonstrates converting a CFG to a PDA that accepts by empty stack, then to one that accepts by final state, and finally back to a CFG.

```python
from pyformlang.cfg import Production, Variable, Terminal, CFG

ter_a = Terminal("a")
ter_b = Terminal("b")
ter_c = Terminal("c")
var_S = Variable("S")
productions = {Production(var_S, [ter_a, var_S, ter_b]),
               Production(var_S, [ter_c])}
cfg = CFG(productions=productions, start_symbol=var_S)

# Convert into a PDA accepting by final state
pda_empty_stack = cfg.to_pda()
# Go to final state
pda_final_state = pda_empty_stack.to_final_state()
# Go back to empty stack, necessary to transform into a CFG
pda_empty_stack = pda_final_state.to_empty_stack()
# Transform the PDA into a CFG
cfg = pda_empty_stack.to_cfg()
```

--------------------------------

### Add Start State Node to Graph

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/finite_automaton.html

Adds a visual representation of a start state to a graph, typically for visualization purposes. It creates a small, unlabeled node connected to the actual start state.

```python
def add_start_state_to_graph(graph, state):
    """ Adds a starting node to a given graph """
    graph.add_node("starting_" + str(state.value),
                   label="",
                   shape=None,
                   height=.0,
                   width=.0)
    graph.add_edge("starting_" + str(state.value),
                   state.value)
```

--------------------------------

### Add a Start State to DFA

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/deterministic_finite_automaton.html

Demonstrates the `add_start_state` method, which sets the initial state for the DFA. The method returns 1 upon successful addition.

```python
>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_start_state(0)
```

--------------------------------

### Create a State Object

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/state.html

Demonstrates how to create a new State object with a given value. This is the basic way to instantiate a state in the finite automaton.

```python
from pyformlang.finite_automaton import State
State("A")
```

--------------------------------

### Remove Start State from DFA

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Removes a specified start state from a DeterministicFiniteAutomaton. Returns 1 if the operation is successful.

```python
>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_start_state(0)
>>> dfa.remove_start_state(0)

```

--------------------------------

### Install Pyformlang Stable Release

Source: https://pyformlang.readthedocs.io/en/latest/_sources/installation.rst.txt

Use this command to install the latest stable version of Pyformlang via pip.

```console
pip3 install pyformlang
```

--------------------------------

### Initialize LL(1) Parser

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/llone_parser.html

Initializes the LLOneParser with a context-free grammar.

```python
from pyformlang.cfg.llone_parser import LLOneParser
from pyformlang.cfg.cfg import CFG

cfg = CFG.from_string("S -> a S b | epsilon")
parser = LLOneParser(cfg)
```

--------------------------------

### Initialize Rules with Optimization

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/indexed_grammar/rules.html

Initializes a Rules object, separating consumption rules and applying an optimization strategy to the order of non-consumption rules. The 'optim' parameter determines the ordering method.

```python
rules = Rules(rules, optim=7)
```

--------------------------------

### Create and Use Regex Objects

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Demonstrates creating Regex objects with various operators and checking word acceptance. It also shows concatenation and conversion to an epsilon NFA.

```python
from pyformlang.regular_expression import Regex

regex = Regex("abc|d")
# Check if the symbol "abc" is accepted
regex.accepts(["abc"])  # True
# Check if the word composed of the symbols
# "a", "b" and "c" is accepted
regex.accepts(["a", "b", "c"])  # False
# Check if the symbol "d" is accepted
regex.accepts(["d"])  # True

regex1 = Regex("a b")
regex_concat = regex.concatenate(regex1)
regex_concat.accepts(["d", "a", "b"])  # True

print(regex_concat.get_tree_str())
# Operator(Concatenation)
#  Operator(Union)
#   Symbol(abc)
#   Symbol(d)
#  Operator(Concatenation)
#   Symbol(a)
#   Symbol(b)

# Give the equivalent finite-state automaton
regex_concat.to_epsilon_nfa()
```

--------------------------------

### PDA Class

Source: https://pyformlang.readthedocs.io/en/latest/modules/push_down_automata.html

Represents a Push-Down Automaton. It can be initialized with states, input symbols, stack alphabet, transition function, start state, start stack symbol, and final states.

```APIDOC
## class pyformlang.pda.PDA

### Description

Representation of a pushdown automaton.

### Parameters

* **states** (set of `State`) - Optional - A finite set of states.
* **input_symbols** (set of `Symbol`) - Optional - A finite set of input symbols.
* **stack_alphabet** (set of `StackSymbol`) - Optional - A finite stack alphabet.
* **transition_function** (`TransitionFunction`) - Optional - Takes as arguments a state, an input symbol and a stack symbol and returns a state and a string of stack symbols push on the stacked to replace X.
* **start_state** (`State`) - Optional - A start state, element of states.
* **start_stack_symbol** (`StackSymbol`) - Optional - The stack is initialized with this stack symbol.
* **final_states** (set of `State`) - Optional - A set of final or accepting states. It is a subset of states.
```

--------------------------------

### Create and Translate Finite State Transducer

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Shows how to create an FST, add transitions, set start and final states, and translate a sequence of symbols.

```python
from pyformlang.fst import FST

fst = FST()
fst.add_transitions(
    [(0, "I", 1, ["Je"]), (1, "am", 2, ["suis"]),
    (2, "happy", 3, ["content"]),
    (2, "happy", 3, ["bien", "content"]),
    (0, "you", 4, ["tu"]), (4, "are", 2, ["es એપ્લિકેશન"]), 
    (0, "you", 5, ["vous"]), (5, "are", 2, ["etes"])]
)
fst.add_start_state(0)
fst.add_final_state(3)
list(fst.translate(["you", "are", "happy"]))
# [['vous', 'etes', 'bien', 'content'],
#  ['vous', 'etes', 'content'],
#  ['tu', 'es', 'bien', 'content'],
#  ['tu', 'es', 'content']]
```

--------------------------------

### Initialize and Add Transition to TransitionFunction

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/transition_function.html

Demonstrates how to create a TransitionFunction object and add a transition between states using a symbol. This is a basic usage pattern for building automaton structures.

```python
transition = TransitionFunction()
transition.add_transition(State(0), Symbol("a"), State(1))
transition.get_number_transitions()
1
```

--------------------------------

### get_closure

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

Gets the Kleene closure of the CFG.

```APIDOC
## get_closure

### Description
Gets the closure of the CFG (*)

### Returns
- **new_cfg** (:class:`~pyformlang.cfg.CFG`) - The CFG representing the Kleene closure.
```

--------------------------------

### Create and Use a Symbol

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/finite_automaton/symbol.html

Demonstrates how to create a Symbol object and its basic usage. Symbols are used to represent individual elements within a finite automaton.

```python
from pyformlang.finite_automaton import Symbol
Symbol("A")
```

--------------------------------

### get_accepted_words

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Gets words accepted by the finite automaton.

```APIDOC
## get_accepted_words

### Description
Gets words accepted by the finite automaton.

### Parameters
#### Path Parameters
- **max_length** (int | None) - Optional - The maximum length of words to retrieve.

### Returns
- Iterable[List[Symbol]] - A list of accepted words, where each word is a list of symbols.
```

--------------------------------

### get_complement

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Gets the complement of the current Epsilon NFA.

```APIDOC
## get_complement

### Description
Gets the complement of the current Epsilon NFA. This operation is equivalent to using the unary minus operator on the automaton object (e.g., `-automaton`).

### Method
get_complement

### Returns
#### Success Response
- **enfa** (EpsilonNFA) - An EpsilonNFA representing the complement of the original automaton.

### Example
```python
enfa = EpsilonNFA()
enfa.add_transitions([(0, "abc", 1), (0, "d", 1), (0, "epsilon", 2)])
enfa.add_start_state(0)
enfa.add_final_state(1)

enfa_complement = enfa.get_complement()

# Example check: the complement should accept words not accepted by the original
print(enfa_complement.accepts(["epsilon"]))
```
```

--------------------------------

### PDA Class Methods

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Provides methods for creating and managing PDA instances, including importing from NetworkX graphs.

```APIDOC
## from_networkx(graph)

### Description
Import a networkx graph into a PDA. The imported graph requires to have the good format, i.e. to come from the function to_networkx.

### Parameters
#### Parameters
- **graph** (type) - Description: The graph representation of the PDA

### Returns
- **pda** (PDA) - A PDA automaton read from the graph

### TODO
* Explain the format
```

--------------------------------

### CFG Initialization

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

Initializes a Context Free Grammar object. It accepts sets of variables, terminals, a start symbol, and productions. If any of these are not provided, they default to empty sets or None. The constructor also ensures that all symbols within productions are added to the respective sets of variables and terminals.

```python
from pyformlang.cfg import CFG, Variable, Terminal, Production

# Example with all parameters
variables = {Variable('S'), Variable('A'), Variable('B')}
terminals = {Terminal('a'), Terminal('b')}
start_symbol = Variable('S')
productions = {
    Production(Variable('S'), [Variable('A'), Terminal('a')]),
    Production(Variable('A'), [Variable('B'), Terminal('b')])
}

cfg_full = CFG(variables=variables, terminals=terminals, start_symbol=start_symbol, productions=productions)

# Example with minimal parameters (only productions)
production1 = Production(Variable('S'), [Variable('A'), Terminal('a')])
production2 = Production(Variable('A'), [Variable('B'), Terminal('b')])
cfg_minimal = CFG(productions={production1, production2})

# Example with string representations for symbols
cfg_strings = CFG(variables={'S', 'A'}, terminals={'a'}, start_symbol='S', productions={Production('S', ['A', 'a'])})

print(cfg_full)
print(cfg_minimal)
print(cfg_strings)

```

--------------------------------

### CFG.get_reachable_symbols

Source: https://pyformlang.readthedocs.io/en/latest/modules/context_free_grammar.html

Identifies and returns all symbols that are reachable from the start symbol in the CFG.

```APIDOC
## get_reachable_symbols

### Description
Gives the objects which are reachable in the CFG.

### Returns
- **reachable_symbols** (set of `CFGObject`) - The reachable symbols of the CFG.
```

--------------------------------

### PDA Initialization

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Initializes a Pushdown Automaton with its components. Supports conversion of input types to internal representations.

```python
import json
from itertools import product
from typing import AbstractSet, List, Iterable, Any

import networkx as nx
import numpy as np
from networkx.drawing.nx_pydot import write_dot

from pyformlang import cfg
from pyformlang import finite_automaton
from pyformlang import regular_expression
from pyformlang.pda.cfg_variable_converter import CFGVariableConverter
from .epsilon import Epsilon
from .stack_symbol import StackSymbol
from .state import State
from .transition_function import TransitionFunction
from .utils import PDAObjectCreator
from ..finite_automaton import FiniteAutomaton
from ..finite_automaton.finite_automaton import add_start_state_to_graph

INPUT_SYMBOL = 1

STACK_FROM = 2

INPUT = 0

STATE = 0

NEW_STACK = 1

OUTPUT = 1




class PDA:
    """ Representation of a pushdown automaton

    Parameters
    ----------
    states : set of :class:`~pyformlang.pda.State`, optional
        A finite set of states
    input_symbols : set of :class:`~pyformlang.pda.Symbol`, optional
        A finite set of input symbols
    stack_alphabet : set of :class:`~pyformlang.pda.StackSymbol`, optional
        A finite stack alphabet
    transition_function : :class:`~pyformlang.pda.TransitionFunction`, optional
        Takes as arguments a state, an input symbol and a stack symbol and
        returns a state and a string of stack symbols push on the stacked to
        replace X
    start_state : :class:`~pyformlang.pda.State`, optional
        A start state, element of states
    start_stack_symbol : :class:`~pyformlang.pda.StackSymbol`, optional
        The stack is initialized with this stack symbol
    final_states : set of :class:`~pyformlang.pda.State`, optional
        A set of final or accepting states. It is a subset of states.
    """

    # pylint: disable=too-many-instance-attributes

    def __init__(self,
                 states: AbstractSet[Any] = None,
                 input_symbols: AbstractSet[Any] = None,
                 stack_alphabet: AbstractSet[Any] = None,
                 transition_function: TransitionFunction = None,
                 start_state: Any = None,
                 start_stack_symbol: Any = None,
                 final_states: AbstractSet[Any] = None):
        # pylint: disable=too-many-arguments
        self._pda_obj_creator = PDAObjectCreator()
        if states is not None:
            states = {self._pda_obj_creator.to_state(x) for x in states}
        if input_symbols is not None:
            input_symbols = {self._pda_obj_creator.to_symbol(x)
                             for x in input_symbols}
        if stack_alphabet is not None:
            stack_alphabet = {self._pda_obj_creator.to_stack_symbol(x)
                              for x in stack_alphabet}
        if start_state is not None:
            start_state = self._pda_obj_creator.to_state(start_state)
        if start_stack_symbol is not None:
            start_stack_symbol =
                self._pda_obj_creator.to_stack_symbol(start_stack_symbol)
        if final_states is not None:
            final_states = {self._pda_obj_creator.to_state(x)
                            for x in final_states}
        self._states = states or set()
        self._states = set(self._states)
        self._input_symbols = input_symbols or set()
        self._input_symbols = set(self._input_symbols)
        self._stack_alphabet = stack_alphabet or set()
        self._stack_alphabet = set(self._stack_alphabet)
        self._transition_function = transition_function or TransitionFunction()
        self._start_state = start_state
        if start_state is not None:
            self._states.add(start_state)
        self._start_stack_symbol = start_stack_symbol
        if start_stack_symbol is not None:
            self._stack_alphabet.add(start_stack_symbol)
        self._final_states = final_states or set()
        self._final_states = set(self._final_states)
        for state in self._final_states:
            self._states.add(state)
        self._cfg_variable_converter = None

```

--------------------------------

### Get CFG Productions

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/cfg.html

Retrieves the set of productions (rules) defined in the CFG.

```python
@property
def productions(self) -> AbstractSet[Production]:
        """ Gives the productions

        Returns
        ----------
        productions : set of :class:`~pyformlang.cfg.Production`
            The productions of the CFG
        """
        return self._productions
```

--------------------------------

### PDA Class Initialization

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/pda/pda.html

Initializes a Pushdown Automaton (PDA) with various components. All parameters are optional and can be set later.

```APIDOC
## PDA

### Description

Represents a push-down automaton. It can be initialized with states, input symbols, stack alphabet, transition function, start state, start stack symbol, and final states.

### Parameters

- **states** (set of :class:`~pyformlang.pda.State`, optional): A finite set of states.
- **input_symbols** (set of :class:`~pyformlang.pda.Symbol`, optional): A finite set of input symbols.
- **stack_alphabet** (set of :class:`~pyformlang.pda.StackSymbol`, optional): A finite stack alphabet.
- **transition_function** (:class:`~pyformlang.pda.TransitionFunction`, optional): Defines the transitions of the PDA.
- **start_state** (:class:`~pyformlang.pda.State`, optional): The initial state of the PDA.
- **start_stack_symbol** (:class:`~pyformlang.pda.StackSymbol`, optional): The initial symbol on the stack.
- **final_states** (set of :class:`~pyformlang.pda.State`, optional): A set of accepting states.
```

--------------------------------

### Get Nonterminals

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/rsa/recursive_automaton.html

Returns a set of all nonterminal symbols present in the recursive automaton.

```python
@property
def nonterminals(self) -> set:
    """ The set of nonterminals """

    return set(self._nonterminal_to_box.keys())
```

--------------------------------

### Initialize NondeterministicFiniteAutomaton

Source: https://pyformlang.readthedocs.io/en/latest/modules/finite_automaton.html

Initializes a NondeterministicFiniteAutomaton. This class forbids epsilon transitions.

```python
>>> nfa = NondeterministicFiniteAutomaton()
```

--------------------------------

### Get FeatureStructure Pointer

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/fcfg/feature_structure.html

Retrieves the pointer of the current feature structure node.

```python
@property
def pointer(self) -> Any:
        """Gets the pointer of the current node"""
        return self._pointer
```

--------------------------------

### Create Push-Down Automaton and Transform Acceptance Types

Source: https://pyformlang.readthedocs.io/en/latest/_sources/usage.rst.txt

Demonstrates the creation of a PDA with explicit states, symbols, and stack symbols, and its transformation between accepting by final state and by empty stack.

```python
from pyformlang.pda import PDA, State, StackSymbol, Symbol, Epsilon

# Declare states
q = State("#STARTTOFINAL#")
q0 = State("q0")

# Declare symbols
e = Symbol("e")
i = Symbol("i")

# Declare stack symbols
Z = StackSymbol("Z")
Z0 = StackSymbol("Z0")

# Create the PDA
pda = PDA(states={q, q0},
              input_symbols={i, e},
              stack_alphabet={Z, Z0},
              start_state=q,
              start_stack_symbol=Z0,
              final_states={q0})

# Add transitions
pda.add_transition(q, i, Z, q, (Z, Z))
pda.add_transition(q, i, Z0, q, (Z, Z0))
pda.add_transition(q, e, Z, q, [])
pda.add_transition(q, Epsilon(), Z0, q0, [])

# Transformation to a PDA accepting by empty stack
pda_empty_stack = pda.to_empty_stack()
# Transformation to a PDA accepting by final state
pda_final_state = pda_empty_stack.to_final_state()
```

--------------------------------

### Initialize Follow Set for LL(1) Parser

Source: https://pyformlang.readthedocs.io/en/latest/_modules/pyformlang/cfg/llone_parser.html

Initializes the follow set and a queue of symbols to process for LL(1) parsing. This is a crucial step in constructing the parsing table.

```python
def _initialize_follow_set(self, first_set):
        to_process = SetQueue()
        follow_set = {}
        follow_set[self._cfg.start_symbol] = {"$"}
        to_process.append(self._cfg.start_symbol)
        for production in self._cfg.productions:
            for i, component in enumerate(production.body):
                for component_next in production.body[i + 1:]:
                    follow_set[component] = follow_set.get(
                        component, set()
                    ).union(first_set.get(component_next, set()))
                    if Epsilon() not in first_set.get(component_next, 
                                                      set()):
                        break
                if Epsilon() in follow_set.get(component, set()):
                    follow_set[component].remove(Epsilon())
                if follow_set.get(component, set()):
                    to_process.append(component)
        return follow_set, to_process
```

--------------------------------

### Get Number of Symbols

Source: https://pyformlang.readthedocs.io/en/latest/modules/regular_expression.html

Returns the total count of symbols within the regular expression.

```APIDOC
## Get Number of Symbols

### Description
Gives the number of symbols in the regex.

### Method
`get_number_symbols() → int`

### Response
#### Success Response (int)
- **n_symbols** (int) - The number of symbols in the regex.

### Request Example
```python
regex = Regex("a|b*")
regex.get_number_symbols()
```

### Response Example
```python
2
```
```