|
|
|
class DFA: |
|
|
|
def __init__( |
|
self, alphabets, states, transition_functions, initial_state, final_states |
|
): |
|
self.alphabets = alphabets |
|
self.states = states |
|
self.transitions = transition_functions |
|
self.initial_state = initial_state |
|
self.final_states = final_states |
|
|
|
|
|
def is_accepting(self, input_string: str): |
|
current_state = self.initial_state |
|
|
|
for char in input_string: |
|
current_state = self.transitions.get(current_state, {}).get( |
|
char, len(self.states) - 1 |
|
) |
|
|
|
return current_state in self.final_states |
|
|
|
|
|
def check(self, paragraph: str): |
|
|
|
if paragraph.strip() == "": |
|
raise ValueError("Empty string provided") |
|
|
|
|
|
paragraph = paragraph.lower().strip() |
|
|
|
|
|
chars = list(paragraph) |
|
|
|
current_word = "" |
|
accepted_words: dict[str : list[tuple[int, int]]] = ( |
|
{} |
|
) |
|
|
|
|
|
word_start = 0 |
|
word_end = 0 |
|
|
|
|
|
for i, char in enumerate(chars): |
|
|
|
if char in self.alphabets: |
|
current_word += char |
|
word_end = i |
|
|
|
|
|
|
|
|
|
|
|
|
|
if char not in self.alphabets or i == len(chars) - 1: |
|
if current_word != "": |
|
if self.is_accepting(current_word): |
|
accepted_words[current_word] = accepted_words.get( |
|
current_word, [] |
|
) + [(word_start, word_end)] |
|
current_word = "" |
|
word_start = i + 1 |
|
|
|
return accepted_words |
|
|
|
|
|
|
|
def generate_dfa(input_strings: list[str]) -> DFA: |
|
alphabets = { |
|
"a", |
|
"b", |
|
"c", |
|
"d", |
|
"e", |
|
"f", |
|
"g", |
|
"h", |
|
"i", |
|
"j", |
|
"k", |
|
"l", |
|
"m", |
|
"n", |
|
"o", |
|
"p", |
|
"q", |
|
"r", |
|
"s", |
|
"t", |
|
"u", |
|
"v", |
|
"w", |
|
"x", |
|
"y", |
|
"z", |
|
} |
|
states = set([0]) |
|
transition_functions = {} |
|
final_states = set() |
|
|
|
for input_string in [ |
|
input_string.lower().strip() for input_string in input_strings |
|
]: |
|
|
|
current_state = 0 |
|
|
|
for i in input_string: |
|
|
|
if i not in alphabets: |
|
raise ValueError(f"Invalid character '{i}' in string '{input_string}'") |
|
|
|
|
|
upcoming_state = transition_functions.get(current_state) |
|
if upcoming_state is not None: |
|
upcoming_state = upcoming_state.get(i) |
|
|
|
|
|
if upcoming_state is None: |
|
|
|
upcoming_state = len(states) |
|
|
|
states.add(upcoming_state) |
|
|
|
if current_state not in transition_functions: |
|
transition_functions[current_state] = {} |
|
transition_functions[current_state][i] = upcoming_state |
|
|
|
|
|
current_state = upcoming_state |
|
|
|
|
|
final_states.add(current_state) |
|
|
|
|
|
states.add(len(states)) |
|
|
|
|
|
for state in states: |
|
if state not in transition_functions: |
|
transition_functions[state] = {} |
|
for alphabet in alphabets: |
|
if alphabet not in transition_functions[state]: |
|
transition_functions[state][alphabet] = len(states) - 1 |
|
|
|
return DFA(alphabets, states, transition_functions, 0, final_states) |
|
|
|
|
|
dfa = generate_dfa(["and", "but", "or", "because"]) |
|
print(dfa.check("me and you.")) |
|
|