CODEWITHSUNDEEP
regexregular-language
Happy Torturer
Happy Torturer

Reputation: 1138

Build a regular expression to define a regular language

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 decision is:

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

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

Upvotes: 0

Views: 90

Answers (2)

Akash
Akash

Reputation: 5221

Your solution will void condition 3. It will ensure only a subchain. For example, it will match 1abab which does not contain aa. Here's one which I have found working:

1a(a[1ab]*|[1ab]*aa[1ab]*)

This begins with 1a. Then based on whether the next character is a (as in 1aa, which will satisfy all 3 conditions btw), searches for any combination of 1, a and b or any combination with an aa in it.

Note: In your notation of formal language, the given regex be like:

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

Upvotes: 3

Felix Frank
Felix Frank

Reputation: 8223

I believe that you cannot form a single regex that will be matched by all and only those strings that match your criteria.

Upvotes: 0

Related Questions