Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings.

For example: Alphabet={a,b,c}; start sub string="ab"; end sub string="cb"

I need to construct DFA which will accept strings of kind: {abcb, abaacb, abcabcb...}.

Question: What algorithm should I use to write function which will construct DFAs for this set of problems.


First, you have to build the regular expression recognizing your language $L$. It should look like this where $p_1,...,p_k$ are the start sub strings and $s_1,...,s_l$ are the end sub strings and $\Sigma$ is your alphabet: $(p_1 | ... | p_k) \Sigma^* (s_1 | ... | s_l)$

In your example, your regular expression is $ab \Sigma^* cb$. Using the Thompson construction, you get a NFA that accepts $L$. This can be transformed into a DFA with the power set construction. As a last step you could minimze the DFA if necessary.

I am not sure if there would be a benefit to use a specialized construction, especially since all the algorithms mentioned above have been implemented and optimized for quite some time.

By the way, a "start substring" is called a prefix, the "end sub string" suffix and a "substring" infix in automata theory.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.