Automata Coding with Python
1. Working with DFA
This imports the DFA class from the [Link] module, which
is part of a Python library for working with finite automata. The DFA
class is used to define and work with Deterministic Finite Automata
(DFA).
from [Link] import DFA
This initializes a DFA object by calling the DFA constructor. The
parameters of this constructor specify the components of the DFA.
# Define a DFA
dfa = DFA(
states={'q0', 'q1', 'q2'},
input_symbols={'0', '1'},
transitions={
'q0': {'0': 'q0', '1': 'q1'},
'q1': {'0': 'q2', '1': 'q0'},
'q2': {'0': 'q1', '1': 'q2'}
},
states is a set of states in the DFA. Here, the DFA has three states:
q0, q1, and q2.
input_symbols is a set of symbols (or alphabet) that the DFA
recognizes. In this case, the DFA accepts the binary digits 0 and 1.
transitions is a dictionary defining the state transition function for
the DFA. It maps a state and an input symbol to another state.
initial_state specifies the starting state of the DFA. Here, the DFA
starts in state q0.
initial_state='q0',
final_states is a set of accepting states. If the DFA ends in one of
these states after processing an input string, the string is
considered accepted. Here, the accepting state is q0.
final_states={'q0'}
# Test if the DFA accepts a string
print(dfa.accepts_input('10101')) # Output: True
The accepts_input method checks whether the DFA accepts the
input string '10101':
Starting from q0, the transitions are as follows:
1 -> q1
0 -> q2
1 -> q2
0 -> q1
1 -> q0 (ends at q0, an accepting state).
The output is True.
print(dfa.accepts_input('111')) # Output: False
print(dfa.accepts_input('111')) # Output: False
The accepts_input method checks whether the DFA accepts the
input string '111':
Starting from q0, the transitions are as follows:
1 -> q1
1 -> q0
1 -> q1 (ends at q1, not an accepting state).
The output is False.
2. Working with Regular Expressions
from [Link] import NFA
from [Link] import DFA
# Convert a regular expression to NFA
This line creates a Non-deterministic Finite Automaton (NFA) from a
regular expression.
nfa = NFA.from_regex(r'0*1*')
regular expression 0*1*.
0*: Matches zero or more occurrences of 0.
1*: Matches zero or more occurrences of 1.
The resulting NFA can accept strings like '0', '1', '0011', '111', '000',
or an empty string, as long as the 0s are followed by 1s in that
order.
Converts the NFA to a Deterministic Finite Automaton (DFA).
dfa = DFA.from_nfa(nfa)
# Check if the DFA accepts a string
print(dfa.accepts_input('01')) # Output: True
print(dfa.accepts_input('10')) # Output: False
3. Palindrome Checker Using DFA
from [Link] import DFA
# DFA for palindromes of length 2 in binary
dfa_palindrome = DFA(
states={'q0', 'q1', 'q2', 'q_accept'},
input_symbols={'0', '1'},
transitions={
'q0': {'0': 'q1', '1': 'q2'},
'q1': {'0': 'q_accept', '1': 'q_accept'},
'q2': {'0': 'q_accept', '1': 'q_accept'},
},
initial_state='q0',
final_states={'q_accept'}
# Test strings
test_strings = ['00', '11', '01', '10']
for string in test_strings:
print(f"String '{string}' is accepted:
{dfa_palindrome.accepts_input(string)}")
4. DFA for Binary Numbers Divisible by 3
from [Link] import DFA
# DFA for binary numbers divisible by 3
This initializes a Deterministic Finite Automaton (DFA) object
representing binary numbers divisible by 3.
dfa_divisible_by_3 = DFA(
states={'q0', 'q1', 'q2'},
input_symbols={'0', '1'},
transitions={
'q0': {'0': 'q0', '1': 'q1'},
'q1': {'0': 'q2', '1': 'q0'},
'q2': {'0': 'q1', '1': 'q2'},
},
initial_state='q0',
final_states={'q0'}
# Test strings
test_strings = ['0', '11', '110', '1011']
for string in test_strings:
print(f"String '{string}' is accepted:
{dfa_divisible_by_3.accepts_input(string)}")
5. Turing Machine for Incrementing a Binary Number
Key Purpose
Binary Incrementer:
The Turing Machine takes a binary number as input and increments
it by 1.
For example:
Input: '101' (binary representation of 5) → Output: '110' (binary
representation of 6).
Input: '111' (binary representation of 7) → Output: '1000' (binary
representation of 8).
from [Link].turing_machine import TuringMachine
# Turing Machine for incrementing a binary number
Initializes a Turing Machine object.
tm_increment: A variable to hold the Turing Machine, which is
designed to perform a binary increment operation.
Defines the set of states in the Turing Machine.
q0: The starting state, where the machine scans the tape for the
end of the binary string.
q1: The state where the machine performs the increment operation
by carrying over.
q2: (Not used in this specific implementation but could be a
placeholder for future operations.)
q_accept: The accepting (final) state indicating the machine has
completed the increment operation.
tape_symbols={'0', '1', 'B'},
Purpose: Defines the set of symbols that can appear on the tape.
Breakdown:
0, 1: Binary digits.
B: Represents a blank symbol, used to mark empty tape cells.
transitions={
Purpose: Specifies the transition function for the Turing Machine.
Breakdown:
The transitions dictionary maps states and tape symbols to actions
in the form (next_state, write_symbol, move_direction).
tm_increment = TuringMachine(
states={'q0', 'q1', 'q2', 'q_accept'},
input_symbols={'0', '1'},
tape_symbols={'0', '1', 'B'},
transitions={
'q0': {'1': ('q0', '1', 'R'), '0': ('q0', '0', 'R'), 'B': ('q1', 'B', 'L')},
'q1': {'1': ('q1', '0', 'L'), '0': ('q_accept', '1', 'N'), 'B': ('q_accept', '1', 'N')}
},
initial_state='q0',
blank_symbol='B',
final_states={'q_accept'}
# Test binary increment
test_tapes = ['101', '111', '1001']
for tape in test_tapes:
print(f"Original: {tape} -> Incremented:
{tm_increment.read_input(tape)}")
Tests the Turing Machine on each tape and prints the result.
Breakdown:
read_input(tape): Simulates the Turing Machine with the given tape
and returns the resulting tape after processing.
The output shows the original binary string and its incremented
value.
Expected Output
'101' (binary 5) -> '110' (binary 6).
'111' (binary 7) -> '1000' (binary 8, with carry).
'1001' (binary 9) -> '1010' (binary 10).