Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
