Create a Python Library for Finite Automata and Regular Languages
Write a Python program to create a library for working with finite automata and regular languages.
Develop a Python library to facilitate operations with finite automata and regular languages. This library should support creating and manipulating both deterministic (DFA) and non-deterministic finite automata (NFA), allowing for the definition of states, transitions, and acceptance conditions. Additionally, it should provide methods for evaluating strings against these automata to determine acceptance, enabling practical applications in pattern recognition and language processing.
Sample Solution:
Python Code :
# Import necessary libraries
from collections import defaultdict
# Define the State class
class State:
def __init__(self, name, is_final=False):
# Initialize state with a name and whether it is a final state
self.name = name
self.is_final = is_final
# Define the Transition class
class Transition:
def __init__(self, from_state, to_state, symbol):
# Initialize transition with source state, destination state, and transition symbol
self.from_state = from_state
self.to_state = to_state
self.symbol = symbol
# Define the FiniteAutomaton class
class FiniteAutomaton:
def __init__(self, states, alphabet, transitions, start_state, final_states):
# Initialize finite automaton with states, alphabet, transitions, start state, and final states
self.states = {state.name: state for state in states}
self.alphabet = alphabet
self.transitions = defaultdict(list)
for t in transitions:
self.transitions[t.from_state.name].append((t.symbol, t.to_state.name))
self.start_state = start_state.name
self.final_states = {state.name for state in final_states}
def is_accepting(self, input_string):
# Determine if the input string is accepted by the automaton
current_state = self.start_state
for symbol in input_string:
if symbol not in self.alphabet:
return False
found = False
for transition_symbol, next_state in self.transitions[current_state]:
if transition_symbol == symbol:
current_state = next_state
found = True
break
if not found:
return False
return current_state in self.final_states
# Define the DFA class, inheriting from FiniteAutomaton
class DFA(FiniteAutomaton):
def __init__(self, states, alphabet, transitions, start_state, final_states):
# Initialize DFA using the FiniteAutomaton initializer
super().__init__(states, alphabet, transitions, start_state, final_states)
# Define the NFA class, inheriting from FiniteAutomaton
class NFA(FiniteAutomaton):
def __init__(self, states, alphabet, transitions, start_state, final_states):
# Initialize NFA using the FiniteAutomaton initializer
super().__init__(states, alphabet, transitions, start_state, final_states)
def is_accepting(self, input_string):
# Determine if the input string is accepted by the NFA using BFS for state exploration
current_states = {self.start_state}
for symbol in input_string:
next_states = set()
for state in current_states:
for transition_symbol, next_state in self.transitions[state]:
if transition_symbol == symbol:
next_states.add(next_state)
current_states = next_states
if not current_states:
return False
return any(state in self.final_states for state in current_states)
# Example usage
if __name__ == "__main__":
# Define states for DFA
s0 = State("S0", is_final=False)
s1 = State("S1", is_final=True)
# Define alphabet for DFA
alphabet = {'0', '1'}
# Define transitions for DFA (accepts strings ending in '0')
transitions = [
Transition(s0, s0, '1'),
Transition(s0, s1, '0'),
Transition(s1, s0, '1'),
Transition(s1, s1, '0')
]
# Create DFA
dfa = DFA(states=[s0, s1], alphabet=alphabet, transitions=transitions, start_state=s0, final_states=[s1])
# Test DFA with some input strings
print(dfa.is_accepting("0")) # Should be True
print(dfa.is_accepting("1")) # Should be False
print(dfa.is_accepting("10")) # Should be True
print(dfa.is_accepting("11")) # Should be False
# Define states for NFA
nfa_s0 = State("S0", is_final=False)
nfa_s1 = State("S1", is_final=True)
# Define alphabet for NFA
nfa_alphabet = {'0', '1'}
# Define transitions for NFA (accepts strings containing at least one '0')
nfa_transitions = [
Transition(nfa_s0, nfa_s0, '1'),
Transition(nfa_s0, nfa_s1, '0'),
Transition(nfa_s1, nfa_s1, '0'),
Transition(nfa_s1, nfa_s1, '1')
]
# Create NFA
nfa = NFA(states=[nfa_s0, nfa_s1], alphabet=nfa_alphabet, transitions=nfa_transitions, start_state=nfa_s0, final_states=[nfa_s1])
# Test NFA with some input strings
print(nfa.is_accepting("0")) # Should be True
print(nfa.is_accepting("1")) # Should be False
print(nfa.is_accepting("10")) # Should be True
print(nfa.is_accepting("11")) # Should be False
Output:
(base) C:\Users\ME>python untitled1.py True False True False True False True False
Explanation:
- State Class: Defines a state with a name and an optional flag for being a final state.
- Transition Class: Represents a transition between states with a given symbol.
- FiniteAutomaton Class: A base class for finite automata with states, alphabet, transitions, a start state, and final states.
- DFA Class: Inherits from "FiniteAutomaton" and represents a deterministic finite automaton.
- NFA Class: Inherits from "FiniteAutomaton" and represents a non-deterministic finite automaton, using BFS for state exploration.
- Example Usage: Demonstrates creating a DFA that accepts strings ending in '0' and an NFA that accepts strings containing at least one '0'.
Python Code Editor :
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics