Combining an odd and even regular expression with a regular grammar?

Question

I have this class for which I need to write a regular grammar. The grammar is {a, b, c}, where there is an odd number a and c, but an even number b.

Examples of good lines:

• V.A.V.S.
• abcb
• cbba
• accaccac
• ace

Bad lines

• babcb
• Abc
• cbbca
• accacca
• aa
• * empty line

My regex for even b b∗(ab∗ab∗)∗b∗(I don't know where to include c)

My regex for odd a (c|a(b|c)*a)*a(b|c)*

My regex for odd with (c|a(b|c)*c)*c(b|c)*

I think a regular grammar would look something like this:

s -> [a], a
s -> [c], c

a -> [a], a
a -> [b], b
a -> [c], c

b -> [b]
b -> [b], b
b -> [a], a
b -> [c], c

c -> [c], c
c -> [a], a
c -> [b], b

It seems to me that I am very lost. Any help is appreciated!

Answer 1

Here is a possible solution in SWI-Prolog:

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

odd_even(Lst) :-
    variables_signature(Lst, Sigs),
    automaton(Sigs, _, Sigs,
              % start in s, end in i
              [source(s), sink(i)],
              % if we meet 0, counter A of a is incremented of one modulo 2
              % the others are unchanged
              [arc(s, 0, s, [(A+1) mod 2, B, C]),
               arc(s, 1, s, [A, (B+1)mod 2, C]),
               arc(s, 2, s, [A, B, (C+1) mod 2]),
               arc(s, 0, i, [(A+1) mod 2, B, C]),
               arc(s, 1, i, [A, (B+1)mod 2, C]),
               arc(s, 2, i, [A, B, (C+1) mod 2])],
              % name of counters
              [A, B, C], 
              % initial values of counters
              [0, 0, 0], 
              % needed final values of counters
              [1,0,1]).

% replace a with 0, b with 1, c with 2
variables_signature(Lst, Sigs) :-
    maplist(\X^Y^(X = a -> Y = 0; (X = b -> Y = 1; Y = 2)), Lst, Sigs).

Example:

?- odd_even([a,c,c,a,c,c,a,c]).
true.

?- odd_even([a,c,c,a,c,c,a]).
false.