## Regular Expression for the following language

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Regular Expression for the following language

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.
a_1_a_5

Posts: 11
Joined: Sun Jan 29, 2012 9:30 am UTC

### Re: Regular Expression for the following language

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.

Proginoskes

Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Regular Expression for the following language

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)*").
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3988
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Regular Expression for the following language

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.

Xeio
Friends, Faidites, Countrymen

Posts: 4409
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\

### Re: Regular Expression for the following language

Xeio wrote: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.

b.i.o
Green is the loneliest number

Posts: 2512
Joined: Fri Jul 27, 2007 4:38 pm UTC
Location: Hong Kong

### Re: Regular Expression for the following language

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
a_1_a_5

Posts: 11
Joined: Sun Jan 29, 2012 9:30 am UTC

### Re: Regular Expression for the following language

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3988
Joined: Tue Feb 20, 2007 12:49 am UTC