ADVANCED
PROGRAMMING
PRACTICE
ASSIGNMENT-13
RA2211026010486
G.Abiram cse-Aiml
Programs:
Sample programs to Construct NFA and DFA using
Python:
1. Write a Python program to create an NFA that
accepts strings containing only the letter 'a'.
Ans:
from pyformlang.finite_automaton import
NondeterministicFiniteAutomaton, State
# Create a state for the initial and final state
state = State(0)
# Create an NFA with a single state that loops on 'a'
nfa = NondeterministicFiniteAutomaton()
nfa.add_start_state(state)
nfa.add_final_state(state)
nfa.add_transition(state, 'a', state)
# Check if a string is accepted
def accepts_string(input_string):
return nfa.accepts(input_string)
# Example usage
input_string = input("Enter a string: ")
if accepts_string(input_string):
print("Accepted!")
else:
print("Not accepted.")
2. Create a Python function to check if a given string is
accepted by an NFA that recognizes
the pattern "ab|ba" (either "ab" or "ba").
Ans:
from pyformlang.finite_automaton import
NondeterministicFiniteAutomaton, State
def create_abba_nfa():
# Create states
state_q0 = State(0)
state_q1 = State(1)
state_q2 = State(2)
state_q3 = State(3)
# Create an NFA with transitions for "ab" and "ba"
nfa = NondeterministicFiniteAutomaton()
nfa.add_start_state(state_q0)
nfa.add_final_state(state_q3)
nfa.add_transition(state_q0, 'a', state_q1)
nfa.add_transition(state_q1, 'b', state_q2)
nfa.add_transition(state_q2, 'a', state_q3)
nfa.add_transition(state_q0, 'b', state_q1)
nfa.add_transition(state_q1, 'a', state_q2)
nfa.add_transition(state_q2, 'b', state_q3)
return nfa
def accepts_abba(input_string):
nfa = create_abba_nfa()
return nfa.accepts(input_string)
# Example usage
input_string = input("Enter a string: ")
if accepts_abba(input_string):
print("Accepted!")
else:
print("Not accepted.")
3. Implement a Python script that converts a simple
NFA into a DFA with two states.
Ans:
from pyformlang.finite_automaton import
NondeterministicFiniteAutomaton,
DeterministicFiniteAutomaton, State
def convert_nfa_to_dfa(nfa):
dfa = DeterministicFiniteAutomaton()
# Create initial state for DFA
dfa_state_0 = State(0)
dfa.add_start_state(dfa_state_0)
# Convert NFA states to DFA states
nfa_to_dfa_states = {frozenset([nfa.start_state]):
dfa_state_0}
unprocessed_states = [frozenset([nfa.start_state])]
while unprocessed_states:
current_nfa_states = unprocessed_states.pop(0)
for symbol in nfa.symbols:
next_nfa_states = set()
for state in current_nfa_states:
next_nfa_states |=
set(nfa.get_transitions(state, symbol))
next_nfa_states = frozenset(next_nfa_states)
if next_nfa_states not in nfa_to_dfa_states:
dfa_state = State(len(nfa_to_dfa_states))
nfa_to_dfa_states[next_nfa_states] =
dfa_state
unprocessed_states.append(next_nfa_states)
dfa.add_transition(nfa_to_dfa_states[current_nfa_stat
es], symbol, nfa_to_dfa_states[next_nfa_states])
# Mark final states in DFA
for dfa_state, nfa_states in
nfa_to_dfa_states.items():
if any(nfa_state in nfa.final_states for nfa_state in
nfa_states):
dfa.add_final_state(dfa_state)
return dfa
# Example usage with an NFA
nfa = NondeterministicFiniteAutomaton()
nfa.add_start_state(State(0))
nfa.add_final_state(State(1))
nfa.add_transition(State(0), 'a', State(1))
nfa.add_transition(State(0), 'b', State(0))
nfa.add_transition(State(1), 'a', State(1))
nfa.add_transition(State(1), 'b', State(1))
dfa = convert_nfa_to_dfa(nfa)
# Print the DFA
print("Converted DFA:")
print(dfa)
4.Write a Python program to construct a DFA that
accepts binary strings ending in '01'.
Ans:
from pyformlang.finite_automaton import
DeterministicFiniteAutomaton, State
def construct_binary_dfa():
dfa = DeterministicFiniteAutomaton()
# Create states
q0 = State(0)
q1 = State(1)
q2 = State(2)
# Add states to DFA
dfa.add_start_state(q0)
dfa.add_final_state(q2)
# Define transitions for '0' and '1'
dfa.add_transition(q0, '0', q0)
dfa.add_transition(q0, '1', q1)
dfa.add_transition(q1, '0', q2)
dfa.add_transition(q1, '1', q1)
dfa.add_transition(q2, '0', q0)
dfa.add_transition(q2, '1', q1)
return dfa
# Example usage
binary_dfa = construct_binary_dfa()
# Print the DFA
print("Binary DFA:")
print(binary_dfa)
5.. Develop a Python function that takes an NFA and
returns the set of states that can be reached
from a given state on a specific input symbol.
Ans:
from pyformlang.finite_automaton import
NondeterministicFiniteAutomaton, State
def get_reachable_states(nfa, start_state,
input_symbol):
# Initialize set to store reachable states
reachable_states = set()
# Initialize stack for DFS traversal
stack = [start_state]
while stack:
current_state = stack.pop()
# Check if the state has a transition on the input
symbol
transitions = nfa.get_transitions(current_state,
input_symbol)
# Add reachable states to the set
reachable_states.update(transitions)
# Add newly discovered states to the stack for
further exploration
stack.extend(transitions - reachable_states)
return reachable_states
# Example usage with an NFA
nfa = NondeterministicFiniteAutomaton()
nfa.add_start_state(State(0))
nfa.add_final_state(State(1))
nfa.add_transition(State(0), 'a', State(1))
nfa.add_transition(State(0), 'b', State(0))
nfa.add_transition(State(1), 'a', State(1))
nfa.add_transition(State(1), 'b', State(1))
start_state = State(0)
input_symbol = 'a'
reachable_states = get_reachable_states(nfa,
start_state, input_symbol)
# Print the set of reachable states
print(f"Reachable states from {start_state} on input
symbol '{input_symbol}': {reachable_states}")
6.. Create a Python script to minimize a simple DFA
with three states by merging equivalent
states.
Ans:
from pyformlang.finite_automaton import
DeterministicFiniteAutomaton, State
def minimize_dfa(dfa):
# Initialize equivalence classes
non_final_states = frozenset(dfa.states -
dfa.final_states)
equivalence_classes = [dfa.final_states,
non_final_states]
# Refine equivalence classes until no further
refinement is possible
while True:
new_equivalence_classes = []
for equiv_class in equivalence_classes:
for symbol in dfa.symbols:
# Group states based on transitions
group = set()
for state in equiv_class:
next_state = dfa.get_transitions(state,
symbol)
group.add(next_state)
# Check if the group is already in the new
equivalence classes
if group not in new_equivalence_classes:
new_equivalence_classes.append(group)
# If no new equivalence classes are found, break
the loop
if new_equivalence_classes ==
equivalence_classes:
break
equivalence_classes = new_equivalence_classes
# Create a new DFA with minimized states
minimized_dfa = DeterministicFiniteAutomaton()
# Map original states to their representative states
in the equivalence classes
state_mapping = {state: min(equiv_class) for
equiv_class in equivalence_classes for state in
equiv_class}
# Add states to the minimized DFA
for equiv_class in equivalence_classes:
representative_state = min(equiv_class)
minimized_dfa.add_state(representative_state)
if representative_state in dfa.start_states:
minimized_dfa.add_start_state(representative_state)
if any(state in dfa.final_states for state in
equiv_class):
minimized_dfa.add_final_state(representative_state)
# Add transitions to the minimized DFA
for equiv_class in equivalence_classes:
representative_state = min(equiv_class)
for symbol in dfa.symbols:
next_state =
dfa.get_transitions(representative_state, symbol)
next_state_representative =
state_mapping[next_state]
minimized_dfa.add_transition(representative_state,
symbol, next_state_representative)
return minimized_dfa
# Example usage with a simple DFA
simple_dfa = DeterministicFiniteAutomaton()
simple_dfa.add_start_state(State(0))
simple_dfa.add_final_state(State(1))
simple_dfa.add_state(State(2))
simple_dfa.add_transition(State(0), 'a', State(1))
simple_dfa.add_transition(State(0), 'b', State(2))
simple_dfa.add_transition(State(1), 'a', State(1))
simple_dfa.add_transition(State(1), 'b', State(2))
simple_dfa.add_transition(State(2), 'a', State(1))
simple_dfa.add_transition(State(2), 'b', State(2))
minimized_dfa = minimize_dfa(simple_dfa)
# Print the original and minimized DFAs
print("Original DFA:")
print(simple_dfa)
print("\nMinimized DFA:")
print(minimized_dfa)
7.. Implement a Python function that checks if a given
string is accepted by a DFA that
recognizes the pattern "ab*c".
Ans:
from pyformlang.finite_automaton import
DeterministicFiniteAutomaton, State
def accepts_dfa_ab_star_c(input_string):
# Create DFA for the pattern "ab*c"
dfa = DeterministicFiniteAutomaton()
q0 = State(0)
q1 = State(1)
q2 = State(2)
dfa.add_start_state(q0)
dfa.add_final_state(q2)
dfa.add_transition(q0, 'a', q1)
dfa.add_transition(q1, 'b', q1)
dfa.add_transition(q1, 'c', q2)
# Check if the input string is accepted by the DFA
current_state = q0
for symbol in input_string:
current_state = dfa.get_transitions(current_state,
symbol)
if current_state is None:
return False
return current_state in dfa.final_states
# Example usage
input_string = input("Enter a string: ")
if accepts_dfa_ab_star_c(input_string):
print("Accepted!")
else:
print("Not accepted.")
8.. Write a Python program to create an NFA that
accepts strings with an odd number of '1's.
Ans:
from pyformlang.finite_automaton import
NondeterministicFiniteAutomaton, State
def create_odd_ones_nfa():
# Create states
q0 = State(0)
q1 = State(1)
# Create an NFA with transitions for odd number of
'1's
nfa = NondeterministicFiniteAutomaton()
nfa.add_start_state(q0)
nfa.add_final_state(q1)
nfa.add_transition(q0, '0', q0)
nfa.add_transition(q0, '1', q1)
nfa.add_transition(q1, '0', q1)
nfa.add_transition(q1, '1', q0)
return nfa
def accepts_odd_ones(input_string):
nfa = create_odd_ones_nfa()
return nfa.accepts(input_string)
# Example usage
input_string = input("Enter a string: ")
if accepts_odd_ones(input_string):
print("Accepted!")
else:
print("Not accepted.")
9.Develop a Python function that converts a simple
regular expression like "a(b|c)*" into an
equivalent NFA.
Ans:
from pyformlang.regular_expression import Regex
from pyformlang.finite_automaton import
NondeterministicFiniteAutomaton, State
def regex_to_nfa(regex_str):
regex = Regex(regex_str)
nfa = regex.to_epsilon_nfa()
return nfa
# Example usage
regex_str = "a(b|c)*"
nfa_equivalent = regex_to_nfa(regex_str)
# Print the equivalent NFA
print("Equivalent NFA:")
print(nfa_equivalent)
