from collections import defaultdict, deque def compute_epsilon_closure(transitions, states): epsilon_closure = defaultdict(set) # Build the epsilon transition map epsilon_map = defaultdict(set) for (state1, symbol, state2) in transitions: if symbol == 'e': epsilon_map[state1].add(state2) def find_closure(state): closure = set() queue = deque([state]) while queue: current_state = queue.popleft() if current_state not in closure: closure.add(current_state) for next_state in epsilon_map[current_state]: if next_state not in closure: queue.append(next_state) return closure # Compute epsilon closure for all states for state in states: epsilon_closure[state] = find_closure(state) return epsilon_closure def main(): # Read input file input_file = 'input.dat' with open(input_file, 'r') as file: transitions = [] for line in file: parts = line.strip().split() if len(parts) == 3: state1, symbol, state2 = parts transitions.append((state1, symbol, state2)) # Extract states from transitions states = set() for (state1, _, state2) in transitions: states.add(state1) states.add(state2) states = sorted(states) # Sort states for consistency in output # Compute epsilon closures epsilon_closures = compute_epsilon_closure(transitions, states) # Print results print(f"Enter the no. of states: {len(states)}") print(f"Enter the states: {' '.join(states)}") for state in states: closure = ' '.join(sorted(epsilon_closures[state])) print(f"Epsilon closure of {state}= {{{closure}}}") if __name__ == "__main__": main()