Regular Expressions

Computer Science Level 1

What regular expression is represented by the finite state machines shown below? $(S_0$ is the starting state. $)$

http://rstb.royalsocietypublishing.org/content/367/1598/1933

a^{*}b^{*}

ab

(ab)^{*}

ab^{*}

a^{*}b

1 solution

Karleigh Moore
Jun 21, 2016

The answer is $a^*b^*$ .

The starting state is $S_0$ but both $S_0$ and $S_1$ are accepting states. Since we start in $S_0$ , we can either stop right away, resulting in an empty string, or transition back to $S_0$ with "a" (we can do this however many times, thus, we have $a^*$ ), or we can transition to $S_1$ with a "b" and once in $S_1$ we can transition back into $S_1$ with another "b" however many times, yielding b*. All put together, the regular expression for this diagram is $a^*b^*$ .

the correct answer should be a bb

Gaurav Pandey - 2 years, 2 months ago

a*b* is the correct solution.

Jorge D. Fochezato - 1 year, 3 months ago

the solutions dont have a b

Alicia Dse - 1 year, 3 months ago

the solutions don't have a b but only ab which opens doors for confusion

Alexander Stefanov - 1 year, 3 months ago

okay the solutions don't have aSTARbSTAR but now we know why haha

Alexander Stefanov - 1 year, 3 months ago

Markdown or some similar formatting is causing the second b to be written in italics. The *s in the answer need to be escaped with a \.

Anders Bäckelie - 1 year, 2 months ago

Regular Expressions

1 solution

0 pending reports