Confusion related to regular expression

Question

I have this confusion related to regular expression. If there are two sets A and B then

is (AB)* = A*B*?

I’m voting to close this question because it is not about programming as defined in the [help center](https://stackoverflow.com/help/on-topic). Might be better suited at [cs.se] — Tomerikoo, May 22 '21 at 14:24

Grijesh Chauhan · Answer 1 · 2013-01-12T10:42:23.270

6

IN CONTEXT OF REGULAR EXPRESSION: is (AB)* = AB?

 No, (AB)* is not equals to A*B*

(AB)* means ABABABABAB......AB A sequence of AB (any number of time).
A*B* means AAAA.....BBB...... Any number of A's followed by any number of B's. And A can't appear after B's.

Intersection - Both includes { NULL string, AB } only

Example:

Suppose: A = xy , and B = z

  (AB)* = xyzxyz.....xyz  
  A*B*  =  xyxyxyxy....zzzz....z

Intersection - Both includes { NULL string, xyz} only.

Example:

Suppose -

  A = {a, b},  
  B = {c, d}

Then,

(AB)* =  ((a + b)(c + d))* , Its language  
L =  { ac, ab, acbd, acac, .....}

NOTE: All string in this language are of even length!

And

A*B*  =   (a + b)* (c + d)* , Its language     
  L = { a, b, c, d, ac, ad, bc, bd, acbd, addb,.........}

NOTE: Also contains odd length strings.

edited Jan 12 '13 at 10:42

answered Nov 13 '12 at 04:50

Grijesh Chauhan

57,103
20
141
208

I understand your `A = ab B = c` example, but it's confusing. I suggest using `A = xy B = z` for clarity. – Justin Morgan - On strike Nov 13 '12 at 06:55
1

changed a,b,c with x,y,z for your continence. Standard is small letter use to denote language symbols and Capital for SET – Grijesh Chauhan Nov 13 '12 at 07:01
Also, one should not use z, x, y, w ... (small alphabetic from last) standard says its for String of language. – Grijesh Chauhan Nov 13 '12 at 11:42
1

The problem is just that `ab` is confusing when you have `A` and `B`. `A = a B = bc` would have worked also. Anyway, one of your upvotes is from me. – Justin Morgan - On strike Nov 13 '12 at 12:50
Thanks @JustinMorgan! I just like to share my knowledge :) . Thanks And Happy Diwali! – Grijesh Chauhan Nov 13 '12 at 12:58

alinsoar · Answer 2 · 2012-11-13T08:31:35.560

1

(AB)* = A*B*  ?

No. The first is the language

 {void, ab, abab, ababab, ...}

the second is the language

{void, a, b, aa, ab, bb, aaa, ...}

edited Nov 13 '12 at 08:31

answered Nov 13 '12 at 07:02

alinsoar

15,386
4
57
74

1

I don't agree with `ba` for the second example. – Tim Pietzcker Nov 13 '12 at 08:18

Confusion related to regular expression

2 Answers2

IN CONTEXT OF REGULAR EXPRESSION: is (AB)* = AB?

Linked

Confusion related to regular expression

2 Answers2

IN CONTEXT OF REGULAR EXPRESSION: is (AB)* = A*B*?

Linked

IN CONTEXT OF REGULAR EXPRESSION: is (AB)* = AB?