search

caleb531 / automata

A Python library for simulating finite automata, pushdown automata, and Turing machines
https://caleb531.github.io/automata/
MIT License
338 stars 63 forks source link

Modelling "garbage" #193

Closed gMontoyaSpeech closed 9 months ago

gMontoyaSpeech commented 9 months ago

Hi all,

Here I am again with more questions. I succeeded with the concatenation of two DFA (DFA -> NFA -> concatenation -> DFA Thank you guys for this info!) but at this stage I was wondering if there's a way to add a some sort of "garbage" arc to my resulting DFA. Let's asume that a have a set of possible inputs (e.g. 30) and I want to accept the string "t a f l @ l" or "t a f l" as shown in the picture. My goal is to be able to add a transition to the initial state ("" / lambda) in every state so that when the incoming input isn't the expected to move forward (one from the 30 input set), it can be sent/reset to the initial state.

image

I hope my question is clear enough!

Thanks a mil :)

EduardoGoulart1 commented 9 months ago

Hi @gMontoyaSpeech I am not sure if I fully understand the request. You cannot have "empty" arcs in a DFA, but you can convert it into an NFA and add the arcs yourself. For that, you need to enable mutable automata (see https://github.com/caleb531/automata/blob/main/docs/class-automaton.md#enabling-mutable-automata)

gMontoyaSpeech commented 9 months ago

Thanks for the answer @EduardoGoulart1 . I already took a look to that piece of documentation but I don't think it could help me in a straightforward way. I didn't mean to have "empty" arcs since I already know what the inputs symbols could be (~ 30 different possible symbols). In the example, I said that I wanted to accept the string "t a f l @ l" or "t a f l". I would also like to be able to accept something like "t a P t a f l". The only way I see to achieve this is to have arcs that at every state that also connect to the initial state. I already get the automata accepting this (manually) but I was just wondering if there was a function that could add multiple symbols to a specific state. It just looks a bit awful to have this piece of code for every single state:

1: {'t': 1, 'a': 2, 'p': 0, 'b': 0, 't': 0, 'd': 0, 'g': 0, 'f': 0, ....

Thank you very much for the help though!

gMontoyaSpeech commented 9 months ago

I'd say this issue can be closed. I might leave the transitions as I described in the previous post or use NFA so that I can add epsilon arcs.

Thanks for your help!