Converting CFG to a regular expression

2.2k Views Asked by At

I have a context free grammar defined by the following rules.

S ->  X .
S ->  Y .
X ->  0 X .
X ->  0 A .
Y ->  Y 1 .
Y ->  A 1 .
A -> e (epsilon)
A -> 0 A 1 .

I know that this creates the following strings (and many more)

1
0
1 1
0 0
1 1 1
0 1 1
0 0 1
0 0 0
1 1 1 1
0 0 0 0
0 1 1 1
0 0 0 1
1 1 1 1 1
0 1 1 1 1
0 0 0 1 1
0 0 1 1 1
0 0 0 0 1
0 0 0 0 0

I think I can define this as

(0^n)(1^m) or (0^m)(1^n) where m<n

but how can I define this formally as a regular expression?