Allow DFA transition function to be partial

[alkkem]

When I studied Automata Theory (and in the literature), the transition function for a DFA could be partial, this is, that there could be some states which do not have an associated transition for a symbol in the alphabet.
In my particular case, I was trying to get this automata:

But, as I said, some states do not have an associated transition for a symbol (take for example state b). This, in principle, accomplishes the DFA restrictions since there is no state such that for a symbol in the alphabet there is more than one associated transition.
When trying to obtain the above DFA using the transition function:

{
'': {'a': 'a', 'b': 'b'},
'a': {'b': 'ab', 'a': 'aa'},
'b': {'b': 'bb'},
'aa': {'a': 'aa', 'b': 'ab'},
'bb': {'a': 'ba'},
'ab': {'b': 'bb'},
'ba': {'a': 'aa'}
}

I get an exception:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/guillermh/.local/lib/python3.9/site-packages/automata/fa/dfa.py", line 23, in __init__
    self.validate()
  File "/home/guillermh/.local/lib/python3.9/site-packages/automata/fa/dfa.py", line 67, in validate
    self._validate_transitions(start_state, paths)
  File "/home/guillermh/.local/lib/python3.9/site-packages/automata/fa/dfa.py", line 59, in _validate_transitions
    self._validate_transition_missing_symbols(start_state, paths)
  File "/home/guillermh/.local/lib/python3.9/site-packages/automata/fa/dfa.py", line 29, in _validate_transition_missing_symbols
    raise exceptions.MissingSymbolError(
automata.base.exceptions.MissingSymbolError: state b is missing transitions for symbol a

I think there is a method _validate_transition_missing_symbols in automata.fa.dfa which is the culprit of this thing.
I would make a pull request but right now I haven't got the time to learn how to implement and run tests and testing code coverage (I'm pretty novice in contributing tasks).
But I opened this issue in order to notify about the possible misconception about the formalities of DFA.
Thank you beforehand!

[caleb531]

@alkkem But... but... it's not a bug, it's a feature! 😝

What you have stumble upon is actually a controversial topic:
https://cs.stackexchange.com/questions/12587/in-a-dfa-does-every-state-have-a-transition-on-every-symbol-of-the-alphabet

In my Automata Theory class in college, I myself was taught that each DFA state must have a transition for every symbol. However, I can understand if this DFA characteristic is subject to debate. Therefore, I will consider adding a method that allows you to toggle this characteristic (maybe an input parameter like allow_partial or something).

I will add it to my backlog of features to work on, and will keep this issue open in the meantime.

[alkkem]

@caleb531 Hehe, you have cited the same page that I found when I was trying to figure out what the problem was.

Thank you for taking this in consideration 😄

[caleb531]

@alkkem You will be pleased to know that I just pushed up a partial DFA option to my in-progress v5 branch. The property is called allow_empty and you can specify it like so:

DFA(
    states={'', 'a', 'b', 'aa', 'bb', 'ab', 'ba'},
    input_symbols={'a', 'b'},
    transitions={
        '': {'a': 'a', 'b': 'b'},
        'a': {'b': 'ab', 'a': 'aa'},
        'b': {'b': 'bb'},
        'aa': {'a': 'aa', 'b': 'ab'},
        'bb': {'a': 'ba'},
        'ab': {'b': 'bb'},
        'ba': {'a': 'aa'}
    },
    initial_state='',
    final_states={'aa'},
    allow_partial=True
)

Please let me know what you think!

[alkkem]

You are awesome!

A boolean parameter thst just solved the neverending discussion... Great!

[caleb531]

@alkkem Alright, I've released Automata v5 with the allow_partial parameter! Hope you enjoy, and let me know if you run into any issues:

https://github.com/caleb531/automata/releases/tag/v5.0.0