Regular Expression for the following language

[a_1_a_5]

All strings over the alphabet {a, b, c, d} with at least four instances of c and at least two instances of a.

So I know this is a regular language. But what would be the regular expression for this.
What i got was the following:

((a|c)*(b|d)*((c|a)(b|d)*)+(b|d)*((c|a)(b|d)*)+(b|d)*((c|a)(b|d)*)+(b|d)*((c|a)(b|d)*)+(b|d)*((a|c)(b|d)*)+(b|d)*((a|c)(b|d)*)+(b|d)*(c|a)*)

However if I try this with something like this: "ccdddddccdddbddddddddddddcdbdbcdbcdbbcdbbcdbcbd"
It still works. But its not supposed to because there are no a's in it. Can anyone help please.

[Proginoskes]

Spoiler:

Code: Select all

((a|b|c|d)*a(a|b|c|d)*a(a|b|c|d)*c(a|b|c|d)*c(a|b|c|d)*c(a|b|c|d)*c(a|b|c|d)*|...)

(where "..." means "and done similarly for all other ordings of aacccc"), i.e., brute force, works but looks very messy.

[Xanthir]

These slides seem to give a decent explanation of the process of converting a DFA to a regex. Unfortunately, the DFA for this language appears to require 15 nodes, so it'll take a little bit of work to hand-convert it. All the examples in those slides are 4 nodes or less.

I suspect it'll end up with a fairly brute-force regex, like what Proginoskes produced, though they could've simplified that a bit (all but the final "(a|b|c|d)*" clause can be simplified to "(b|d)*").

[Xeio]

Should I ask the obvious question of why you want to do this in a regex? The're really bad at anything requires state (counting, in addition to others) except in nearly trivial cases.

[b.i.o]

Should I ask the obvious question of why you want to do this in a regex?

Because it was assigned as a homework problem, I'd bet.

[a_1_a_5]

Well it can be either a CFG, or a regular expression....but I believe it is a regular expression...but I'm not to sure...so if someone can clarify it'll be helpful

[Xanthir]

This is definitely a regular language, and it's not a complicated DFA. It'll just be a fairly long regex.

Spoiler:

The DFA is a simple 3x5 array. Start in the upper left. When you detect an A, move right. When you detect a C, move down. B or D, loop in your current state. If you reach the bottom-right, success! Just loop there forever.