finding a DFA that fits the description

Question

I wanted to know if there's a way of building a minimal DFA that represents the next situation :A DFA that accepts a string that the last 4 letters of the input represent a valid representation of brackets.

what I mean by valid: ()() , (()), the empty string.

none valid brackets: (((( ,())) and such

above the alpha bet {$ ($ , $) $}

I tried solving this question but have failed to do so. Any help will be gladly accepted!

Answer 1

Yes, this is possible, for any finite set of strings it's possible to construct a DFA containing all strings that have a suffix in that set. Such a DFA can grow exponentially big though.

A simple way to make such a DFA (that isn't minimal, but works) is to simply make one state for every single suffix that's possible. E.g. for $\{0, 1\}^*$ with suffix length $3$ we have eight states:

000   100
001   101
010   110
011   111

Then any of these suffixes you consider valid you mark as an accepting state.

Then you connect these states. E.g. $000$ gets an edge to $001$ when an $1$ is an encountered. And $110$ gets an edge to $010$ when an $0$ is encountered.

Finally you make one state for each string shorter than the suffix lengths, in this case:

""
0
1
00
01
10
11

And connect them appropriately. Finally you mark the empty string as the initial state.

After this you can minimize the automaton.