# Build a regular expression to define a regular language [duplicate]

The language is an infinite set of chains that are defined by the next conditions.

Conditions:

1) The language chains may consist of symbols from the set {1,a,b}.
2) The language chains always start from subchain '1a'.
3) Every languange chain has to include at least one subchain 'aa'.


For example:

1aa, 1abaa, 1aaab, 1aab1a, ... etc.


My current solution is this:

1a ((1+b)* a)* (a (1+b)*)* a (1+b+a)*


My solution seems to pass tests like these:

Allowed chains    : 1aa, 1aaa, 1abaa, 1aaba, 1aabaa, 1aab, 1aaab, 1aaabaaa
Not allowed chains: 1aba, 1abab, 1ababab


But I'm not quite sure if it's still correct. Is it correct?

If not, please offer your solution using only the type of formal language used in my solution.

• But how to do this without priority parens ()? Using only iteration parens ()* is allowed. May 15 '14 at 11:35
• Why should we just use parens in combination with the star-operator? May 15 '14 at 11:38
• Because I was told to use only the star-operator. So there's no solution without using the star-operator only? My solution seems to be Okay. If you see any kind of mistake in my solution, I would be grateful if you tell me about it. May 15 '14 at 11:51
• Your solution seems to be right, but you also use 'concatenation' and 'or' in your solution.. so I do not understand why we can use everything except priority brackets. But if you want to do so, your expression seems to be fine. May 15 '14 at 12:09
• @Danny Your regexp is wrong: it doesn't match $1aab$. May 15 '14 at 15:21

One way to do it by hand, in such a simple case, would be to build a FA for condition 2, i.e. strings that start with $1a$, and another FA for condition 3, i.e. strings that contain $aa$. Both FAs have only 3 states.

Then you use the intersection construction to have an automaton that obeys both conditions. That remains simple enough if you organize your state pairs as a 3 by 3 matrix.

From that you can easily deduce a regular expression: $1(a+a(a+b+1)^*a)a(a+b+1)^*$

Your solution can be proved consistent (compliant with the stated conditions) with a case analysis over the two main star operators (cases depending on whether there is zero occurrence or at least one). One also has to prove it is complete, i.e. that it does cover all compliant strings.

If you have a constraint regarding the use of parentheses, you should state it in your question. Is there a reason for the constraint ?