[Solved]: Describe in English the pattern in the following regular expressions

Problem Detail: 

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible

#1 (x (yyy + x)*)* #2 (c (cc)*d(dd)*)* 

for number 1 I got all words in which when y is in the word it can only appear in blocks that are divisible by 3(0,3,6,9, etc.)

the second question I can not see any type of pattern.

I would like to know if the first one is correct, and if what pattern is on the second one?

Thanks

Asked By : tommycatpr

Answered By : Patrick87

The first one is very close, but not quite right. Your phrasing technically allows strings that start with $yyy$, but the language contains no such string. There are lots of ways to fix what you have to incorporate this. For instance, you might try "all strings in which $y$s appear only in blocks of length divisible by $3$ preceded by at least one $x$." You'll want to check that to make sure it's right, of course.

The second one isn't too bad. Notice that a description of the regular expression inside the outermost parentheses might be "an odd number of $c$s followed by an odd number of $d$s." By applying the Kleene star, we allow this to be repeated an arbitrary number of times. Something like "All strings which, if non-empty, start with a $c$, end with a $d$ and alternate blocks of $c$s and $d$s of odd lengths," should be close.

Some general pointers:

1. Work from the inside out. Describe the subexpressions first, and use those descriptions to describe expressions.

2. If you're not seeing a pattern, it never hurts to write out some representative strings.

3. Pay special attention to boundary cases, especially around the empty string. Natural language tends to be a little unclear when it comes to things existing, satisfying properties vacuously, etc.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29629