Given the language below, how do i find a regular expression for the language
L = {a ^n b ^m | n => 1, m =>1, nm =>3}
+1
A:
n>=1 and m>=1 and nm>=3 is true for each of the following:
n=1,m>=3
n>=3,m=1
n>=2,m>=2
So L = { abbb, abbbb, abbbbb, ... } U { aaab, aaaab, aaaaab, ... } U { a^n b^m | n>=2,m>=2 }
This regex should be equivalent to L:
((abbb(b*)) | (aaa(a*)b) | (aa(a*)bb(b*)))
There is probably a much more succinct answer than this.
Sean A.O. Harney
2010-03-24 21:14:48
What does the notation "n => 1, m =>1, nm =>3" mean. Even having seen your answer I can't figure it out?
Martin Smith
2010-03-24 21:21:17
Oh and kayn if this answered your question you should mark it as answered!
Martin Smith
2010-03-24 21:23:15
It means for integers n and m, n >= 1 AND m >= 1 AND n*m >= 3. In set builder notation, {a ^ n | n >= 0 } = { <empty>, a, aa, aaa, aaaa, ... }
Sean A.O. Harney
2010-03-24 21:24:58
@Sean the >= symbols are reversed though... looks like an arrow, if that could make any sense.
NomeN
2010-03-24 21:29:47
@Sean, i get your solution but am not sure why we have to include the last part where n>=2,m>=2
kayn
2010-03-24 21:32:35
Ah right - I did wonder if it was >=. Thanks!
Martin Smith
2010-03-24 21:32:50
@NoMeN Yes I reversed them, >=,=>, same meaning.
Sean A.O. Harney
2010-03-24 21:36:06
@kayn: since it is n=>1 and m=>1 and nm=>3 we need that last part. n=2,m=2 and n=3,m=30 and so on are all valid.
Sean A.O. Harney
2010-03-24 21:39:38
@kayn: We need to include "aabb". The answer could be (aa*bbbb* | aaaa*bb* | aabb)
David Thornley
2010-03-24 21:43:59
Re: succinctness: I think the most readable (for a completely subjective definition of "readable", of course) formulation is probably the one I hinted at at the end of my answer. However, I won't write that down just yet. You know, teach a man to fish and all that stuff.
Jörg W Mittag
2010-03-24 21:50:04
I would also like to give a regular expression for the language over ∑ = {a,b,c} so that any string in the language have at least one occurrence of each symbol.How would i represent this?
kayn
2010-03-24 21:52:54
+1
A:
Write down a set of example words of the language. Get a feel for them. Look for patterns. Look for common prefixes / suffixes / substrings.
abbb
abbbb
abbbbb
aabb
aabbb
aabbbb
aaab
aaabb
aaabbb
aaaab
aaaabb
aaaabbb
For example: notice that all words start with a and end with b. So, your regular expression looks something like a...b. What does the ... part look like?
bb
bbb
bbbb
ab
abb
abbb
aa
aab
aabb
aaa
aaab
aaabb
This kinda looks like either an a followed by either at least one a or a b possibly followed by zero or more bs. Or simply a series of more than two bs.
a(a+|b)b*|b{2,}
You could also say it is either a series of at least two as or a series of at least two bs or a series of as followed by bs. I'm not going to write down that expression.
This is homework, after all, so I'll leave it to you to desugar this and put it together with the first result. (BTW: all the shortcuts I used are just syntactic sugar and they do not make regular expressions more powerful. I.e. there is a simple syntactic transformation that turns them into standard regular expression.)
[I just hope I'm right and don't make an ass of myself :-)]
Jörg W Mittag
2010-03-24 21:39:08