-2

Construct a regular expression that defines the language M (say) containing all words beginning with exactly one a or exactly one b. (Words in M are at least of length 1 and words such as aa, bbbaba and aaaabbabbbabb do not belong to M. Words in M can begin and end with the same letter substring or begin and end with different letter substrings.) I want to know if i can can simplify my answer and is my answer correct .

My answer is :

(aba*+baa*+a*ab+aa*b+ba*a+a*ba)+(b*ab+bab*+b*ba+bb*a+ab*b+abb*)
CiaPan
  • 13,049
Veekash Singh
  • 1
  • 1
    Certainly what you have isn’t right. It doesn’t accept the strings $a$, $abab$, $baaab$, and so on. – mjqxxxx Jun 05 '23 at 13:29

2 Answers2

1

You have not specified an alphabet; I assume, based on word examples, it contains two symbols only, 'a' and 'b'.

A word may be a single letter 'a' or 'b', or another letters may follow—but then the second letter must differ from the first one. That means if the first letter is 'a', then the next one must be 'b' (if present at all), and similarly, after the starting 'b' the 'a' must go.

So the corresponding reg-exp can be

a(b[ab]*)?|b(a[ab]*)?
  • 'a' with or without a following group, consisting of a single 'b' and any number (including zero) of 'a' and 'b' in any possible sequence,

or

  • 'b' with or without a following group, consisting of a single 'a' and any number (including zero) of 'a' and 'b' in any possible sequence.

Another way of defining M:

a|b|(ab|ba)[ab]*
  • a single 'a'
  • a single 'b'
  • 'ab' or 'ba', followed by any number (inluding zero) of 'a' and 'b' in any possible sequence.
CiaPan
  • 13,049
0

I cant quite understand your answer as it uses some special '$a$' character which is different from 'a' for some reason? However here is a solution that should be minimal where $\Sigma = \{a,b\}$:

$M = \{a,b\}+ab\Sigma^*+ba\Sigma^*$

Ok as clarified, it looks like your 'a's all are the same, then your answer is wrong and wont work. The question asks us to accept words that have exactly one 'a' or one 'b', your answer does not accept the single letter words 'a' and 'b'. To answer questions like this it is best to seperate the language into multiple 'classes' of words that are similar in this case we have two classes, words that start with 'a' and words that start with 'b', notice we have another two classes namely words that have exactly one letter and words that have atleast two letters. These turn out to be the equivalence classes from the Myhill-Nerode theorem but that isnt important right now.

So you can now tackle each case individually and take a union of them. I'll leave it to you to identify each case in my answer.

Niranjan Kumar
  • 173
  • He’s not doing it that way on purpose; some quirk of MathJax is displaying it that way. – mjqxxxx Jun 05 '23 at 13:32
  • 1
    The special 'a' and 'b' characters were resulting from markup interpreter using regexp asterisks for its own purpose (namely, to make a font italic). I have edited the question so that the whole regexp displays properly – you may want to revise and adjust your answer. Hope you can forgive me an additional work you may need to do with your answer now. – CiaPan Jun 05 '23 at 14:27