I have this DFA described as (Q, q1, A, N, F) where
Q = {1,2,3,4},
q1 = 1,
A = {a,b,c},
F = {2,4},
N = {
(1,a) -> 2, (1,b) -> 3, (1,c) -> 4,
(2,a) -> 2, (2,b) -> 4,
(3,a) -> 2, (3,c) -> 4,
(4,b) -> 4, (4,c) -> 4 }
So I have drawn the transition diagram, and that looks fine,
I then need to work out wether or not the following strings are acceptable by this DFA:
and come up with the following
I am not 100% sure those are correct, but think they are on the right track.
I then need to describe the language this accepts, in english, which I do not see being a problem, but where I need help is describing this language using mathematical notation. Could you please help me to understand this.
Thanks so much for your help
Your answers about the strings acceptability are right, this can easily be seen by trying to follow them out in the diagram.
Now, about the language:
In the 2-nd vertex we can finish with the words corresponding following regular expression:
b?a+ - we can optionally obtain b my moving to 3-rd vertex first, and then pass over a, or we can move to 2-nd vertex by a at once, and there we can add as much as as we want.
Now about finishing the word in the 4-th vertex:
First, how can we reach vertex 4 ?
1. We can first time reach vertex 4 by moving there by c at once, or by moving to 3-rd vertex first, obtaining b, and then to 4-th by c. Hereby we get strings like b?c
2. We can reach vertex 2 with b?a+ (as described in previous case), and then pass over b. Hereby we get strings like b?a+b.
Totally, we can reach to 4-th vertex with any word matching the b?(a+b|c) regexp.
Now, adding arbitrary count of b and c symbols in the end on vertex 4, we get the answer for this case:
b?(a+b|c)(bc)*
Finally, we can result the whole set of words acceptable by this DFA words as the following regex:
b?( a+ | (a+b|c)(bc)*? )