Unashamedly asking for homework help: regex gurus needed

[KingNothing]

You are given the following alphabet: {a,b,c,d}

Write a regular expression describing the set of all identifiers (i.e., strings) having at most 2 occurrences of the letter c. For example, the identifier "abbcdaac" would belong to this set, but the identifier "aabcdaacc" would not.

 

[manly]

[abd]*c?[abd]*c?[abd]*

 

[wolf550e]

Why wouldn't "aabcdaac" belong? It's from the alphabet and has two c's.

 

[KingNothing]

Originally posted by: wolf550e
Why wouldn't "aabcdaac" belong? It's from the alphabet and has two c's.

I'm a tard, I left out the third c in that one. Sorry.

 

[KingNothing]

Originally posted by: manly
[abd]*c?[abd]*c?[abd]*

that one matches the "bad" string

 

[manly]

Originally posted by: KingNothing

Originally posted by: manly
[abd]*c?[abd]*c?[abd]*

that one matches the "bad" string

Your examples are still incorrect, and you should tell me why my regexp is wrong.

 

[KingNothing]

Ok...examples are definitely correct this time, and your regexp is wrong because it matched a string with more than two c's in it.

 

[manly]

Originally posted by: KingNothing
Ok...examples are definitely correct this time, and your regexp is wrong because it matched a string with more than two c's in it.

And how does my regexp do that?

 

[mattlear]

Originally posted by: manly
[abd]*c?[abd]*c?[abd]*

It's been a while since I've done/used regular expressions, but I believe the above is correct.

It's basically saying:

[abd]* = 0 to infinte combinations of a, b, and/or d followed by
c? = 0 or 1 occurance of the letter c followed by
[abd]* = (same as first one)
c? = same as second followed by
[abd]*

That would, in effect, give all strings from the set {a,b,c,d} where c occurs at most 2 times in the string (but not limited to c occuring once or not at all)

-Matt

 

[HJB417]

aaaahhh!!!!! i already forgot everything I learned in theory of computation

 

[KingNothing]

Originally posted by: manly

Originally posted by: KingNothing
Ok...examples are definitely correct this time, and your regexp is wrong because it matched a string with more than two c's in it.

And how does my regexp do that?

$ cat filelist
aabcdaacc
aabdccdaf
abacabacabac
abaccc
abbcdaac
file
filelist

$ egrep "[abd]*c?[abd]*c?[abd]*" filelist
aabcdaacc
aabdccdaf
abacabacabac
abaccc
abbcdaac
file
filelist

$ egrep "[abcd]+" filelist
aabcdaacc
aabdccdaf
abacabacabac
abaccc
abbcdaac

If there's something wrong with my testing method, let me know.

 

[KingNothing]

bump, still

 

[KingNothing]

help

 

[notfred]

What regex metacharacters are you allowed to use? In my comp. theory class we were only allowed to use *, +, ( and ). (+ was for or, as opposed to perl using | for or)

Anyway, an expression that matches at most two 'c's?

I'm using perl regexes here because they're a lot shorter than ones with abbreviated metacharacter sets, but you should be able to translate easily enough.

[^c]*c?[^c]*c?[^c]*

And since you suck at grep, I've edited it already so you don't tell me it's wrong like you did with manly's identical and also correct regex.

edited version: ^[^c]*c?[^c]*c?[^c]*$

Note that grep seems to choke on the trailing $ if you're using tcsh. Also, Of course you're getting it to match strings that end with multiple 'c's cause you don't know how grep works. It matches any portion of the string if you don't include the ^ and $ anchors for the beginning and end of the line.

 

[StormRider]

I think what egrep does is to print the entire line if there is a match to the pattern within the line. I think Manly is correct.

Originally posted by: KingNothing

Originally posted by: manly

Originally posted by: KingNothing
Ok...examples are definitely correct this time, and your regexp is wrong because it matched a string with more than two c's in it.

And how does my regexp do that?

$ cat filelist
aabcdaacc
aabdccdaf
abacabacabac
abaccc
abbcdaac
file
filelist

$ egrep "[abd]*c?[abd]*c?[abd]*" filelist
aabcdaacc
aabdccdaf
abacabacabac
abaccc
abbcdaac
file
filelist

$ egrep "[abcd]+" filelist
aabcdaacc
aabdccdaf
abacabacabac
abaccc
abbcdaac

If there's something wrong with my testing method, let me know.