### Initialize NTM with Example Configuration

Source: https://caleb531.github.io/automata/api/tm/class-ntm

This code snippet shows how to instantiate the NTM class, defining its states, input and tape symbols, transitions, initial state, blank symbol, and final states. It models a Turing machine that accepts strings starting with '0's followed by an equal number of '1's.

```python
from automata.tm.ntm import NTM
# NTM which matches all strings beginning with '0's, and followed by
# the same number of '1's
# Note that the nondeterminism is not really used here.
ntm = NTM(
    states={'q0', 'q1', 'q2', 'q3', 'q4'},
    input_symbols={'0', '1'},
    tape_symbols={'0', '1', 'x', 'y', '.'},
    transitions={
        'q0': {
            '0': {('q1', 'x', 'R')},
            'y': {('q3', 'y', 'R')},
        },
        'q1': {
            '0': {('q1', '0', 'R')},
            '1': {('q2', 'y', 'L')},
            'y': {('q1', 'y', 'R')},
        },
        'q2': {
            '0': {('q2', '0', 'L')},
            'x': {('q0', 'x', 'R')},
            'y': {('q2', 'y', 'L')},
        },
        'q3': {
            'y': {('q3', 'y', 'R')},
            '.': {('q4', '.', 'R')},
        }
    },
    initial_state='q0',
    blank_symbol='.',
    final_states={'q4'}
)

```

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

### Install Automata Library with Visual Dependencies

Source: https://caleb531.github.io/automata/index

Installs the Automata library along with optional visual dependencies. This is useful if you plan to use the library's visualization features and require external packages like pygraphviz.

```bash
pip install 'automata-lib[visual]'
```

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

### Install Automata Library via Pip

Source: https://caleb531.github.io/automata/index

Installs the latest version of the Automata library using pip. This is the standard method for adding the library to your Python environment.

```bash
pip install automata-lib
```

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

### Generate Transition Table from Finite Automaton

Source: https://caleb531.github.io/automata/examples/fa-examples

This function takes a DFA or NFA and returns its transition table as a pandas DataFrame. It iterates through the transitions of the finite automaton, formatting state names and symbols for clarity. Start states are prefixed with '→' and final states with '*'. It depends on the 'pandas' library for DataFrame creation. The input is a finite automaton object (DFA or NFA), and the output is a pandas DataFrame representing the transition table.

```python
import pandas as pd

def make_table(target_fa) -> pd.DataFrame:
    initial_state = target_fa.initial_state
    final_states = target_fa.final_states

    table = {}

    for from_state, to_state, symbol in target_fa.iter_transitions():
        # Prepare nice string for from_state
        if isinstance(from_state, frozenset):
            from_state_str = str(set(from_state))
        else:
            from_state_str = str(from_state)

        if from_state in final_states:
            from_state_str = "*" + from_state_str
        if from_state == initial_state:
            from_state_str = "→" + from_state_str

        # Prepare nice string for to_state
        if isinstance(to_state, frozenset):
            to_state_str = str(set(to_state))
        else:
            to_state_str = str(to_state)

        if to_state in final_states:
            to_state_str = "*" + to_state_str

        # Prepare nice symbol
        if symbol == "":
            symbol = "λ"

        from_state_dict = table.setdefault(from_state_str, dict())
        from_state_dict.setdefault(symbol, set()).add(to_state_str)

    # Reformat table for singleton sets
    for symbol_dict in table.values():
        for symbol in symbol_dict:
            if len(symbol_dict[symbol]) == 1:
                symbol_dict[symbol] = symbol_dict[symbol].pop()


    df = pd.DataFrame.from_dict(table).fillna("∅").T
    return df.reindex(sorted(df.columns), axis=1)

```

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

### Prefix DFA Construction

Source: https://caleb531.github.io/automata/api/fa/class-dfa

Constructs a minimal DFA that accepts strings starting with a given prefix.

```APIDOC
## from_prefix(input_symbols, prefix, *, contains=True, as_partial=True)

### Description
Directly computes the minimal DFA accepting strings with the given prefix. If `contains` is set to `False` then the complement is constructed instead.

### Method
*Class Method*

### Parameters
#### Path Parameters
- **input_symbols** (AbstractSet[str]) - Required - The set of input symbols to construct the DFA over.
- **prefix** (str) - Required - The prefix of strings that are accepted by this DFA.
- **contains** (bool) - Optional - Whether or not to construct the compliment DFA. Defaults to True.
- **as_partial** (bool) - Optional - Whether or not to construct this DFA as a partial DFA. Defaults to True.

### Returns
#### Success Response
- **Self** (DFA) - The DFA accepting the desired language.
```

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

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

Source: https://caleb531.github.io/automata/examples/fa-examples

Demonstrates the creation of a DFA that accepts all binary strings ending in an odd number of '1's. It includes defining states, input symbols, transitions, initial state, and final states. The DFA diagram can be generated, and it can be used with the user input function.

```python
from automata.fa.dfa import DFA

# DFA which matches all binary strings ending in an odd number of '1's
my_dfa = DFA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q0', '1': 'q2'},
        'q2': {'0': 'q2', '1': 'q1'}
    },
    initial_state='q0',
    final_states={'q1'}
)

my_dfa.show_diagram()
read_user_input(my_dfa)
```

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

### Immutable DFA Instance Creation in Automata v7

Source: https://caleb531.github.io/automata/migration

Demonstrates how to create a new DFA instance with modified parameters, reflecting the immutability introduced in Automata v7. It shows retrieving input parameters, modifying them, and then constructing a new DFA object.

```python
from automata.fa.dfa import DFA

dfa1 = DFA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q0', '1': 'q2'},
        'q2': {'0': 'q2', '1': 'q1'}
    },
    initial_state='q0',
    final_states={'q1'}
)
# You can still copy an automaton just fine
dfa2 = dfa1.copy() # Corrected from 'dfa.copy()' to 'dfa1.copy()'
# If you want to make a change, you must create a new instance; please note
# that dfa2.input_parameters is always a deep copy of the input parameters for
# dfa2 (in other words, mutating dfa2.input_parameters will not actually mutate
# dfa2)
params = dfa2.input_parameters
params['final_states'] = {'q2'}
dfa3 = DFA(**params)
```

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

### Read User Input for Automata

Source: https://caleb531.github.io/automata/examples/fa-examples

Defines a function that takes an automaton object and prompts the user for input strings. It then prints whether the automaton accepts or rejects each input string. The loop continues until a KeyboardInterrupt (Ctrl+C) is received.

```python
def read_user_input(my_automaton):
    try:
        while True:
            if my_automaton.accepts_input(input("Please enter your input: ")):
                print("Accepted")
            else:
                print("Rejected")
    except KeyboardInterrupt:
        print("")
```

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

### Instantiate MNTM - Python

Source: https://caleb531.github.io/automata/api/tm/class-mntm

Demonstrates how to instantiate an MNTM (Multitape Nondeterministic Turing Machine) with specified states, symbols, tapes, transitions, initial state, blank symbol, and final states. This example shows a machine that accepts all strings in {0, 1}* and writes all 1's from the first tape to the second tape.

```python
from automata.tm.mntm import MNTM
# MNTM which accepts all strings in {0, 1}* and writes all
# 1's from the first tape (input) to the second tape.
self.mntm1 = MNTM(
    states={'q0', 'q1'},
    input_symbols={'0', '1'},
    tape_symbols={'0', '1', '#'},
    n_tapes=2,
    transitions={
        'q0': {
            ('1', '#'): [('q0', (('1', 'R'), ('1', 'R')))],
            ('0', '#'): [('q0', (('0', 'R'), ('#', 'N')))],
            ('#', '#'): [('q1', (('#', 'N'), ('#', 'N')))],
        }
    },
    initial_state='q0',
    blank_symbol='#',
    final_states={'q1'},
)

```

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

### Remove Constructor Polymorphism: Convert NFA to DFA

Source: https://caleb531.github.io/automata/migration

Illustrates the change in how to convert a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite Automaton (DFA). The direct constructor approach is replaced by a static factory method `from_nfa()`.

```python
dfa = DFA(nfa)
```

```python
dfa = DFA.from_nfa(nfa)
```

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

### Minimize DFA from Large Randomized Regex using Python

Source: https://caleb531.github.io/automata/examples/perf-examples

This Python script demonstrates minimizing a Deterministic Finite Automaton (DFA) generated from a large, randomized regular expression. It uses the 'automata' library to convert a regex to a Non-deterministic Finite Automaton (NFA) and then to a minimized DFA. The script measures the time taken for NFA and DFA construction, and prints information about the resulting DFA, such as the number of states and accepted words. Dependencies include the 'automata' and 'random' libraries.

```python
# Do imports
import random
import time

from automata.fa.dfa import DFA
from automata.fa.nfa import NFA

# Define regex parameters
num_clauses = 1_000
clause_size = 50

# Define the input symbols and randomly
# construct the regex
input_symbols = ["0", "1"]
raw_regex = "|".join(
    ""
    .join(random.choices(input_symbols, k=clause_size))
    for _ in range(num_clauses)
)

# Convert the regex to NFA
start = time.perf_counter()
regex_nfa = NFA.from_regex(raw_regex)
end = time.perf_counter()
print(
    f"Created equivalent NFA with {len(regex_nfa.states):,} states in {end-start:4f} seconds."
)

# Convert to (minimized) DFA
start = time.perf_counter()
regex_dfa = DFA.from_nfa(regex_nfa, minify=True)
end = time.perf_counter()

# Print timing and other information
print(
    f"Created equivalent minimized DFA with {len(regex_dfa.states):,} states in {end-start:4f} seconds."
)
print(f"Number of words accepted by DFA: {len(regex_dfa):,}.")
print(f"Minimum word length accepted by DFA: {regex_dfa.minimum_word_length():,}.")
print(f"Maximum word length accepted by DFA: {regex_dfa.minimum_word_length():,}.")

```

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

### Define and Use a Nondeterministic Finite Automaton (NFA)

Source: https://caleb531.github.io/automata/examples/fa-examples

Shows how to define an NFA that accepts strings beginning with 'a', ending with 'a', and containing no consecutive 'b's. It highlights the different transition dictionary structure compared to DFAs. The NFA diagram can be generated, and it can be used with the user input function.

```python
from automata.fa.nfa import NFA

# NFA which matches strings beginning with "a", ending with "a", and
# containing no consecutive "b"s
my_nfa = NFA(
    states={"q0", "q1", "q2"},
    input_symbols={"a", "b"},
    transitions={
        "q0": {"a": {"q1"}},
        "q1": {"a": {"q1"}, "": {"q2"}},
        "q2": {"b": {"q0"}},
    },
    initial_state="q0",
    final_states={"q1"},
)

my_nfa.show_diagram()
read_user_input(my_nfa)
```

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

### Initialize DTM for matching 0s followed by 1s

Source: https://caleb531.github.io/automata/api/tm/class-dtm

Initializes a Deterministic Turing Machine (DTM) to accept strings starting with a sequence of '0's followed by an equal number of '1's. This involves defining states, input/tape symbols, transition rules, initial state, blank symbol, and final states.

```python
from automata.tm.dtm import DTM
# DTM which matches all strings beginning with '0's, and followed by
# the same number of '1's
dtman = DTM(
    states={'q0', 'q1', 'q2', 'q3', 'q4'},
    input_symbols={'0', '1'},
    tape_symbols={'0', '1', 'x', 'y', '.'},
    transitions={
        'q0': {
            '0': ('q1', 'x', 'R'),
            'y': ('q3', 'y', 'R')
        },
        'q1': {
            '0': ('q1', '0', 'R'),
            '1': ('q2', 'y', 'L'),
            'y': ('q1', 'y', 'R')
        },
        'q2': {
            '0': ('q2', '0', 'L'),
            'x': ('q0', 'x', 'R'),
            'y': ('q2', 'y', 'L')
        },
        'q3': {
            'y': ('q3', 'y', 'R'),
            '.': ('q4', '.', 'R')
        }
    },
    initial_state='q0',
    blank_symbol='.',
    final_states={'q4'}
)

```

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

### Remove Constructor Polymorphism: Convert DFA to NFA

Source: https://caleb531.github.io/automata/migration

Shows the updated method for converting a Deterministic Finite Automaton (DFA) to a Non-deterministic Finite Automaton (NFA). Similar to NFA to DFA conversion, the constructor is replaced by a static factory method `from_dfa()`.

```python
nfa = NFA(dfa)
```

```python
nfa = NFA.from_dfa(dfa)
```

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

### Generate Words Within Edit Distance using NFA/DFA

Source: https://caleb531.github.io/automata/examples/fa-examples

This function determines which strings in a given set are within a specified edit distance from a reference string. It constructs an edit distance NFA, intersects it with a DFA recognizing the target words, and returns the matching words. Dependencies include the 'automata' library for NFA and DFA operations and the 'string' module for input symbols. It takes an integer edit distance, a string reference string, and a set of target words as input, returning a set of strings.

```python
import string

from automata.fa.dfa import DFA
from automata.fa.nfa import NFA


def words_within_edit_distance(edit_distance, reference_string, target_words):
    input_symbols = set(string.ascii_lowercase)

    # Construct DFA recognizing target words
    target_words_dfa = DFA.from_finite_language(
        input_symbols,
        target_words,
    )

    # Next, construct NFA recognizing all strings
    # within given edit distance of target word
    words_within_edit_distance_dfa = DFA.from_nfa(
        NFA.edit_distance(
            input_symbols,
            reference_string,
            edit_distance,
        )
    )

    # Take intersection and return results
    found_words_dfa = target_words_dfa & words_within_edit_distance_dfa
    return set(found_words_dfa)


target_words = {"these", "are", "target", "words", "them", "those"}
reference_string = "they"
edit_distance = 2

found_words = words_within_edit_distance(edit_distance, reference_string, target_words)

# Set is {"these", "them"}
print(
    f"All words within edit distance {edit_distance} of "
    f"'{reference_string}': {found_words}"
)

```

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

### Edit Distance DFA for Large Dictionaries using Python

Source: https://caleb531.github.io/automata/examples/perf-examples

This Python script constructs a DFA that recognizes all words in a large English dictionary within a specified edit distance of a target word. It utilizes the automata library for DFA and NFA operations, including creating a DFA from a finite language and converting an NFA to a DFA. The script measures the time taken for DFA construction and intersection, and prints the found words. Dependencies include the 'automata', 'pooch', and 'string' libraries.

```python
# Imports from automata library
import string
import time

import pooch

from automata.fa.dfa import DFA
from automata.fa.nfa import NFA

# First, get a set of all the words we'd like to use
word_file = pooch.retrieve(
    url="https://raw.githubusercontent.com/solardiz/wordlists/master/gutenberg-all-lowercase-words.txt",
    known_hash="62be81d8a5cb2dae11b96bdf85568436b137b9c0961340569ca1fca595774788",
)

with open(word_file, "r") as wf:
    word_set = set(wf.read().splitlines())


print(f"Word set size: {len(word_set):,}")

# Create the DFA recognizing all the words we'd like
# NOTE this DFA is minimal by construction
start = time.perf_counter()
input_symbols = set(string.ascii_lowercase)
word_dfa = DFA.from_finite_language(input_symbols, word_set)
end = time.perf_counter()

print(f"Created recognizing DFA in {end-start:4f} seconds.")
print(f"States in DFA: {len(word_dfa.states):,}")

# Create the automaton recognizing words close to our target
# word from an NFA
target_word = "those"
edit_distance = 2

edit_distance_dfa = DFA.from_nfa(
    NFA.edit_distance(
        input_symbols,
        target_word,
        edit_distance,
    )
)

# Finally, take intersection and print results
start = time.perf_counter()
found_words_dfa = word_dfa & edit_distance_dfa
found_words = list(found_words_dfa)
end = time.perf_counter()

print(f"DFA intersection done in {end-start:4f} seconds.")
print(
    f"All words within edit distance {edit_distance} of "
    f'"{target_word}": {found_words}'
)

```

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

### NPDA Class Initialization

Source: https://caleb531.github.io/automata/api/pda/class-npda

Initializes an NPDA instance with states, symbols, transitions, and acceptance criteria.

```APIDOC
## NPDA Class

### Description
The `NPDA` class is a subclass of `PDA` and represents a nondeterministic pushdown automaton.

### Parameters
#### Path Parameters
- **states** (AbstractSet[NPDAStateT]) - Required - A set of the NPDA's valid states
- **input_symbols** (AbstractSet[str]) - Required - Set of the NPDA's valid input symbols, each of which is a singleton string.
- **stack_symbols** (AbstractSet[str]) - Required - Set of the NPDA's valid stack symbols, each of which is a singleton string.
- **transitions** (NPDATransitionsT) - Required - A dict consisting of the transitions for each state; see the example below for the exact syntax
- **initial_state** (NPDAStateT) - Required - The name of the initial state for this NPDA.
- **initial_stack_symbol** (str) - Required - The name of the initial symbol on the stack for this NPDA.
- **final_states** (AbstractSet[NPDAStateT]) - Required - A set of final states for this NPDA.
- **acceptance_mode** (PDAAcceptanceModeT) - Optional - A string defining whether this NPDA accepts by 'final_state', 'empty_stack', or 'both'. Default: 'both'

### Request Example
```python
from automata.pda.npda import NPDA

# NPDA which matches palindromes consisting of 'a's and 'b's
# (accepting by final state)
# q0 reads the first half of the word, q1 the other half, q2 accepts.
# But we have to guess when to switch.
npda = NPDA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'a', 'b'},
    stack_symbols={'A', 'B', '#'},
    transitions={
        'q0': {
            '': {
                '#': {('q2', '#')},  # no change to stack
            },
            'a': {
                '#': {('q0', ('A', '#'))},  # push 'A' to stack
                'A': {
                    ('q0', ('A', 'A')),  # push 'A' to stack
                    ('q1', ''),  # pop from stack
                },
                'B': {('q0', ('A', 'B'))},  # push 'A' to stack
            },
            'b': {
                '#': {('q0', ('B', '#'))},  # push 'B' to stack
                'A': {('q0', ('B', 'A'))},  # push 'B' to stack
                'B': {
                    ('q0', ('B', 'B')),  # push 'B' to stack
                    ('q1', ''),  # pop from stack
                },
            },
        },
        'q1': {
            '': {'#': {('q2', '#')}},  # push '#' to (currently empty) stack
            'a': {'A': {('q1', '')}},  # pop from stack
            'b': {'B': {('q1', '')}},  # pop from stack
        },
    },
    initial_state='q0',
    initial_stack_symbol='#',
    final_states={'q2'},
    acceptance_mode='final_state'
)
```

### Response
#### Success Response (200)
- **NPDA instance**: An initialized NPDA object.

#### Response Example
```json
{
  "message": "NPDA initialized successfully"
}
```
```

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

### Rename Method: validate_self to validate

Source: https://caleb531.github.io/automata/migration

Shows the renaming of the automaton self-validation method from `validate_self()` to `validate()`. This simplification improves consistency in the library's API.

```python
dfa.validate_self()
```

```python
dfa.validate()
```

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

### DPDA Initialization

Source: https://caleb531.github.io/automata/api/pda/class-dpda

Initializes a Deterministic Pushdown Automaton (DPDA) with specified states, symbols, transitions, and acceptance criteria.

```APIDOC
## DPDA

### Description
The `DPDA` class is a subclass of `PDA` and represents a deterministic pushdown automaton.

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **states** (AbstractSet[DPDAStateT]) - Required - A set of the DPDA's valid states
- **input_symbols** (AbstractSet[str]) - Required - Set of the DPDA's valid input symbols, each of which is a singleton string.
- **stack_symbols** (AbstractSet[str]) - Required - Set of the DPDA's valid stack symbols, each of which is a singleton string.
- **transitions** (DPDATransitionsT) - Required - A dict consisting of the transitions for each state; see the example below for the exact syntax
- **initial_state** (DPDAStateT) - Required - The name of the initial state for this DPDA.
- **initial_stack_symbol** (str) - Required - The name of the initial symbol on the stack for this DPDA.
- **final_states** (AbstractSet[DPDAStateT]) - Required - A set of final states for this DPDA.
- **acceptance_mode** (PDAAcceptanceModeT) - Optional - A string defining whether this DPDA accepts by 'final_state', 'empty_stack', or 'both'. Default: 'both'

### Request Example
```json
{
  "states": ["q0", "q1", "q2", "q3"],
  "input_symbols": ["a", "b"],
  "stack_symbols": ["0", "1"],
  "transitions": {
    "q0": {
      "a": {"0": ["q1", ["1", "0"]]}  
    },
    "q1": {
      "a": {"1": ["q1", ["1", "1"]],}, 
      "b": {"1": ["q2", ""]} 
    },
    "q2": {
      "b": {"1": ["q2", ""]},
      "": {"0": ["q3", ["0"]]} 
    }
  },
  "initial_state": "q0",
  "initial_stack_symbol": "0",
  "final_states": ["q3"],
  "acceptance_mode": "final_state"
}
```

### Response
#### Success Response (200)
Returns an initialized DPDA object.

#### Response Example
```json
{
  "message": "DPDA initialized successfully"
}
```
```

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

### Remove Constructor Polymorphism: Copying Automaton

Source: https://caleb531.github.io/automata/migration

Demonstrates the removal of constructor-based copying for Automata. Previously, an automaton could be copied by passing it to the constructor. Now, the `copy()` method should be used instead.

```python
dfa = DFA(dfa)
```

```python
dfa = dfa.copy()
```

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

### Rename Method: validate_input to read_input and read_input_stepwise

Source: https://caleb531.github.io/automata/migration

Illustrates the renaming of input validation methods in the Automata library. `validate_input()` is now `read_input()`, and its step-by-step variant is `read_input_stepwise()`. This change aims for clearer method naming.

```python
final_state = dfa.validate_input('0011')
steps = dfa.validate_input('0011', step=True)
```

```python
final_state = dfa.read_input('0011')
steps = dfa.read_input_stepwise('0011')
```

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

### DFA Class Initialization

Source: https://caleb531.github.io/automata/api/fa/class-dfa

Initializes a new DFA instance. It requires sets of states, input symbols, transitions, an initial state, and final states.

```APIDOC
## DFA Class

### Description
Initializes a new DFA instance. It requires sets of states, input symbols, transitions, an initial state, and final states. The `allow_partial` parameter can be set to `True` to permit states with fewer transitions than input symbols.

### Method
`__init__`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **states** (AbstractSet[DFAStateT]) - Required - Set of the DFA's valid states.
- **input_symbols** (AbstractSet[str]) - Required - Set of the DFA's valid input symbols, each of which is a singleton string.
- **transitions** (Mapping[DFAStateT, Mapping[str, DFAStateT]]) - Required - Dict consisting of the transitions for each state. Each key is a state name, and each value is another dict which maps a symbol (the key) to a state (the value).
- **initial_state** (DFAStateT) - Required - The initial state for this DFA.
- **final_states** (AbstractSet[DFAStateT]) - Required - A set of final states for this DFA.
- **allow_partial** (bool) - Optional - By default, each DFA state must have a transition to every input symbol; if this parameter is `True`, you can disable this characteristic. Defaults to `False`.

### Request Example
```json
{
  "states": "set of states",
  "input_symbols": "set of symbols",
  "transitions": "mapping of state to (symbol to state)",
  "initial_state": "initial state",
  "final_states": "set of final states",
  "allow_partial": false
}
```

### Response
#### Success Response (200)
None (Initialization method)

#### Response Example
None
```

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

### Update Module Path: automata.shared to automata.base

Source: https://caleb531.github.io/automata/migration

This code snippet demonstrates the change in import paths from `automata.shared` to `automata.base` to reflect internal module restructuring. It shows how to update imports for `Automaton` and `FinalStateError`.

```python
from automata.shared.automaton import Automaton
from automata.shared.exceptions import FinalStateError
```

```python
from automata.base.automaton import Automaton
from automata.base.exceptions import FinalStateError
```

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

### Initialize DPDA Automaton

Source: https://caleb531.github.io/automata/api/pda/class-dpda

Initializes a Deterministic Pushdown Automaton (DPDA) with specified states, symbols, transitions, initial configuration, final states, and acceptance mode. This DPDA recognizes strings with zero or more 'a's followed by an equal number of 'b's.

```python
from automata.pda.dpda import DPDA

dpda = DPDA(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'a', 'b'},
    stack_symbols={'0', '1'},
    transitions={
        'q0': {
            'a': {'0': ('q1', ('1', '0'))}  # push '1' to stack
        },
        'q1': {
            'a': {'1': ('q1', ('1', '1'))},  # push '1' to stack
            'b': {'1': ('q2', '')}  # pop from stack
        },
        'q2': {
            'b': {'1': ('q2', '')},  # pop from stack
            '': {'0': ('q3', ('0',))}  # no change to stack
        }
    },
    initial_state='q0',
    initial_stack_symbol='0',
    final_states={'q3'},
    acceptance_mode='final_state'
)

```

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

### Rename Exception Classes: *Error to *Exception

Source: https://caleb531.github.io/automata/migration

This snippet highlights the renaming of general exception classes from ending in `Error` to `Exception` (e.g., `AutomatonError` to `AutomatonException`). This aligns with Python's standard exception naming conventions.

```python
from automata.shared.exceptions import AutomatonError
from automata.shared.exceptions import RejectionError
from automata.pda.exceptions import PDAError
from automata.tm.exceptions import TMError
```

```python
from automata.base.exceptions import AutomatonException
from automata.base.exceptions import RejectionException
from automata.pda.exceptions import PDAException
from automata.tm.exceptions import TMException
```

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

### NFA Initialization from Regex

Source: https://caleb531.github.io/automata/api/fa/class-nfa

Initializes a new NFA instance based on a given regular expression.

```APIDOC
## NFA.from_regex(regex, *, input_symbols=None)

### Description
Initialize this NFA as one equivalent to the given regular expression.

### Method
`classmethod`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```python
# Example usage (conceptual):
# nfa = NFA.from_regex("a*b")
```

### Response
#### Success Response (200)
- **Self** (NFA) - The NFA accepting the language of the input regex.

#### Response Example
```json
{
  "example": "NFA object initialized from regex"
}
```

### Raises
None
```

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

### Check NFA Subset Relationship

Source: https://caleb531.github.io/automata/examples/fa-examples

Implements a function to determine if one NFA is a subset of another. This is achieved by checking if the union of the two NFAs is equal to the second NFA, implying that the first NFA does not accept any strings that the second NFA does not. NFAs can be created from regular expressions.

```python
import string
from automata.fa.nfa import NFA

def is_subset(nfa1, nfa2):
    # In the following, we have nfa1 and nfa2 and want to determine whether
    # nfa1 is a subset of nfa2.

    # If taking the union of nfa2 with nfa1 is equal to nfa2 again,
    # nfa1 didn't accept any strings that nfa2 did not, so it is a subset.
    return nfa1.union(nfa2) == nfa2

alphabet = set(string.ascii_lowercase)

nfa1 = NFA.from_regex("abc", input_symbols=alphabet)
nfa2 = NFA.from_regex("(abc)|(def)", input_symbols=alphabet)
nfa3 = NFA.from_regex("a*bc", input_symbols=alphabet)

print(is_subset(nfa1, nfa2))  # True
print(is_subset(nfa1, nfa3))  # True
print(is_subset(nfa2, nfa3))  # False
```

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

### NTM Constructor

Source: https://caleb531.github.io/automata/api/tm/class-ntm

Initializes a nondeterministic Turing machine (NTM).

```APIDOC
## NTM Constructor

### Description
Initializes a nondeterministic Turing machine (NTM).

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
- **states** (AbstractSet[NTMStateT]) - Required - A set of the NTM's valid states.
- **input_symbols** (AbstractSet[str]) - Required - Set of the NTM's valid input symbols, each of which is a singleton string.
- **tape_symbols** (AbstractSet[str]) - Required - Set of the NTM's valid tape symbols, each of which is a singleton string.
- **transitions** (NTMTransitionsT) - Required - Dict consisting of the transitions for each state; each key is a state name, and each value is a dict which maps a symbol (the key) to a set of tuples consisting of the next state, the symbol to write on the tape, and the direction to move the tape head.
- **initial_state** (NTMStateT) - Required - The name of the initial state for this NTM.
- **blank_symbol** (str) - Required - A symbol from `tape_symbols` to be used as the blank symbol for this NTM.
- **final_states** (AbstractSet[NTMStateT]) - Required - A set of final states for this NTM.

### Request Example
```python
{
  "states": "set of states",
  "input_symbols": "set of input symbols",
  "tape_symbols": "set of tape symbols",
  "transitions": "dictionary of transitions",
  "initial_state": "initial state",
  "blank_symbol": "blank symbol",
  "final_states": "set of final states"
}
```

### Response
#### Success Response (200)
None

#### Response Example
None
```

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

### GNFA Class Methods

Source: https://caleb531.github.io/automata/api/fa/class-gnfa

Class methods and instance methods for GNFA operations, including initialization from other automata, iterating transitions, converting to regex, and validation.

```APIDOC
## GNFA Class Methods

### Description
Provides methods for creating GNFAs from DFAs and NFAs, iterating through transitions, converting the GNFA to a regular expression, and validating the GNFA's internal consistency.

### Methods

#### `from_dfa(target_dfa)`

##### Description
Initializes this GNFA as one equivalent to the given DFA.

##### Parameters
- **target_dfa** (DFA) - Required - The DFA to construct an equivalent GNFA for.

##### Returns
- **Self** - The GNFA accepting the language of the input DFA.

#### `from_nfa(target_nfa)`

##### Description
Initializes this GNFA as one equivalent to the given NFA.

##### Parameters
- **target_nfa** (NFA) - Required - The NFA to construct an equivalent GNFA for.

##### Returns
- **Self** - The GNFA accepting the language of the input NFA.

#### `iter_transitions()`

##### Description
Iterates over all transitions in the GNFA. Each transition is a tuple of the form (from_state, to_state, symbol).

##### Returns
- **Generator[Tuple[GNFAStateT, GNFAStateT, str], None, None]** - The desired generator over the GNFA transitions.

#### `to_regex()`

##### Description
Converts the GNFA to a regular expression.

##### Returns
- **str** - A regular expression equivalent to the input GNFA.

#### `validate()`

##### Description
Raises an exception if this automaton is not internally consistent.

##### Raises
- **InvalidStateError** - If this GNFA has invalid states in the transition dictionary.
- **MissingStateError** - If this GNFA has states missing from the transition dictionary.
- **InvalidRegexError** - If this GNFA has invalid regex in the transition dictionary.
```

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

### DFA Construction APIs

Source: https://caleb531.github.io/automata/api/fa/class-dfa

Class methods to directly construct minimal DFAs for specific language properties.

```APIDOC
## POST /dfa/nth_from_end

### Description
Directly computes the minimal DFA which accepts all words whose `n`th character from the end is `symbol`.

### Method
POST

### Endpoint
/dfa/nth_from_end

### Parameters
#### Request Body
- **input_symbols** (AbstractSet[str]) - Required - The set of input symbols to construct the DFA over.
- **symbol** (str) - Required - The target input symbol.
- **n** (int) - Required - The position of the target input symbol (positive integer).

### Request Example
```json
{
  "input_symbols": ["a", "b"],
  "symbol": "a",
  "n": 2
}
```

### Response
#### Success Response (200)
- **Self** (DFA) - The DFA accepting the desired language.

#### Response Example
```json
{
  "dfa": {
    "states": ["q0", "q1", "q2"],
    "input_symbols": ["a", "b"],
    "transitions": [
      {"from": "q0", "to": "q0", "symbol": "a"},
      {"from": "q0", "to": "q0", "symbol": "b"},
      {"from": "q1", "to": "q2", "symbol": "a"},
      {"from": "q1", "to": "q1", "symbol": "b"},
      {"from": "q2", "to": "q0", "symbol": "a"},
      {"from": "q2", "to": "q1", "symbol": "b"}
    ],
    "initial_state": "q0",
    "final_states": ["q2"]
  }
}
```
```

```APIDOC
## POST /dfa/nth_from_start

### Description
Directly computes the minimal DFA which accepts all words whose `n`th character from the start is `symbol`.

### Method
POST

### Endpoint
/dfa/nth_from_start

### Parameters
#### Request Body
- **input_symbols** (AbstractSet[str]) - Required - The set of input symbols to construct the DFA over.
- **symbol** (str) - Required - The target input symbol.
- **n** (int) - Required - The position of the target input symbol (positive integer).

### Request Example
```json
{
  "input_symbols": ["a", "b"],
  "symbol": "b",
  "n": 1
}
```

### Response
#### Success Response (200)
- **Self** (DFA) - The DFA accepting the desired language.

#### Response Example
```json
{
  "dfa": {
    "states": ["q0", "q1"],
    "input_symbols": ["a", "b"],
    "transitions": [
      {"from": "q0", "to": "q0", "symbol": "a"},
      {"from": "q0", "to": "q1", "symbol": "b"},
      {"from": "q1", "to": "q1", "symbol": "a"},
      {"from": "q1", "to": "q1", "symbol": "b"}
    ],
    "initial_state": "q0",
    "final_states": ["q1"]
  }
}
```
```

```APIDOC
## POST /dfa/of_length

### Description
Directly computes the minimal DFA recognizing strings whose length is between `min_length` and `max_length`, inclusive.

### Method
POST

### Endpoint
/dfa/of_length

### Parameters
#### Request Body
- **input_symbols** (AbstractSet[str]) - Required - The set of input symbols to construct the DFA over.
- **min_length** (int) - Optional - The minimum length of strings to be accepted by this DFA. Defaults to 0.
- **max_length** (Optional[int]) - Optional - The maximum length of strings to be accepted by this DFA. If set to None, there is no maximum. Defaults to None.
- **symbols_to_count** (Optional[AbstractSet[str]]) - Optional - The input symbols to count towards the length of words to accepts. If set to None, counts all symbols. Defaults to None.

### Request Example
```json
{
  "input_symbols": ["0", "1"],
  "min_length": 2,
  "max_length": 4
}
```

### Response
#### Success Response (200)
- **Self** (DFA) - The DFA accepting the desired language.

#### Response Example
```json
{
  "dfa": {
    "states": ["q0", "q1", "q2", "q3", "q4"],
    "input_symbols": ["0", "1"],
    "transitions": [
      {"from": "q0", "to": "q1", "symbol": "0"},
      {"from": "q0", "to": "q1", "symbol": "1"},
      {"from": "q1", "to": "q2", "symbol": "0"},
      {"from": "q1", "to": "q2", "symbol": "1"},
      {"from": "q2", "to": "q3", "symbol": "0"},
      {"from": "q2", "to": "q3", "symbol": "1"},
      {"from": "q3", "to": "q4", "symbol": "0"},
      {"from": "q3", "to": "q4", "symbol": "1"},
      {"from": "q4", "to": "q4", "symbol": "0"},
      {"from": "q4", "to": "q4", "symbol": "1"}
    ],
    "initial_state": "q0",
    "final_states": ["q2", "q3", "q4"]
  }
}
```
```

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

### read_input_stepwise

Source: https://caleb531.github.io/automata/api/pda/class-dpda

Processes an input string step by step, yielding the DPDA's configuration at each stage.

```APIDOC
## read_input_stepwise(input_str)

### Description
Return a generator that yields the configuration of this DPDA at each step while reading input.

### Method
GET (or POST, depending on implementation, assuming GET for read-only operation)

### Endpoint
`/websites/caleb531_github_io_automata/DPDA/read_input_stepwise`

### Parameters
#### Path Parameters
None

#### Query Parameters
- **input_str** (str) - Required - The input string to read.

#### Request Body
None

### Request Example
```json
{
  "input_str": "ab"
}
```

### Response
#### Success Response (200)
- **PDAConfiguration** (Generator) - A generator that yields the current configuration of the DPDA after each step of reading input.

#### Response Example
```json
{
  "yields": [
    {"state": "q0", "stack": "0"},
    {"state": "q1", "stack": "10"},
    {"state": "q2", "stack": "0"}
  ]
}
```

#### Error Response
- **RejectionException** - Raised if this DPDA does not accept the input string.
```

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

### from_dfa(target_dfa)

Source: https://caleb531.github.io/automata/api/fa/class-nfa

A class method that initializes an NFA that is equivalent to a given Deterministic Finite Automaton (DFA). The resulting NFA will accept the same language as the input DFA.

```APIDOC
## `from_dfa(target_dfa)` ##

### Description
Initialize this NFA as one equivalent to the given DFA.

### Method
POST

### Endpoint
`/websites/caleb531_github_io_automata/NFA/from_dfa`

### Parameters
#### Request Body
- **target_dfa** (DFA) - Required - The DFA to construct an equivalent NFA for.

### Response
#### Success Response (200)
- **NFA** (Self) - The NFA accepting the language of the input DFA.
```

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

### Empty Language DFA Construction

Source: https://caleb531.github.io/automata/api/fa/class-dfa

Constructs a minimal DFA that rejects all strings.

```APIDOC
## empty_language(input_symbols)

### Description
Directly computes the minimal DFA rejecting all strings.

### Method
*Class Method*

### Parameters
#### Path Parameters
- **input_symbols** (AbstractSet[str]) - Required - The set of input symbols to construct the DFA over.

### Returns
#### Success Response
- **Self** (DFA) - The DFA accepting the desired language.
```