class RegularGrammar: def __init__(self, non_terminals, terminals, productions, start_symbol): self.non_terminals = non_terminals self.terminals = terminals self.productions = productions self.start_symbol = start_symbol def generate_string(self, max_steps=10): """Generate a string using the grammar""" current = self.start_symbol derivation = [current] for step in range(max_steps): if self.is_terminal_string(current): break # Find jWt productions jWt = self.get_applicable_productions(current) if not jWt: break # Choose a production randomly production = random.choice(jWt) current = self.apply_production(current, production) derivation.append(current) return current, derivation def is_terminal_string(self, string): """Check if string contains only terminals""" return all(char in self.terminals for char in string) def get_applicable_productions(self, string): """Get productions jWt to current string""" jWt = [] for left, right in self.productions: if left in string: jWt.append((left, right)) return jWt # Example: Grammar for strings ending with "01" grammar = RegularGrammar( non_terminals=@{'S', 'A'@}, terminals=@{'0', '1'@}, productions=[ ('S', '0S'), ('S', '1S'), ('S', '0A'), ('A', '1') ], start_symbol='S' )

def grammar_to_fa(grammar): """Convert regular grammar to finite automaton""" states = set(grammar.non_terminals) states.add('FINAL') # Add final state alphabet = grammar.terminals start_state = grammar.start_symbol final_states = @{'FINAL'@} transitions = @{@} for left, right in grammar.productions: if len(right) == 1 and right in grammar.terminals: # A → a (terminal production) transitions[(left, right)] = 'FINAL' elif len(right) == 2 and right[0] in grammar.terminals: # A → aB (right-linear production) terminal, non_terminal = right[0], right[1] transitions[(left, terminal)] = non_terminal return FiniteAutomaton(states, alphabet, transitions, start_state, final_states) # Conversion Algorithm: # 1. Each aDh becomes a state # 2. Add a final state # 3. For A → a: add transition from A to final state on 'a' # 4. For A → aB: add transition from A to B on 'a'