Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Regular expression kleene closure and concatenation confusion. Here is what I think I understand amongst the regular expressions given: a+bc => either a or bc

Regular expression kleene closure and concatenation confusion.

Here is what I think I understand amongst the regular expressions given:

a+bc => either a or bc

a(b+c) => a concatenated with either a or c

a*(b+cc) => a (as many times) concatenated with b or cc. The a is either not there or there as many times, but the b and cc remains the same quantity.

a*b* => a (as many times) concatenated with b (as many times). Can give aaaaaaaab, aaabbbbbb, etc.

a+bb* => a or b concatenated with b (as many times). In the example of string bbbbb, the first b is the non-kleene star b then the others are the kleene star b as many times.

The regular expression (a+bb)* is where it confuses me.

I interpret it as: a (as many times) or b concatenated with b (bb) as many times (bb together as many times not separate).

I understand how the strings can be aa, aaaa, aaaaa (as many times) etc. Same for bb, bbbb, bbbbb, etc. However, because of the union wouldn't that mean that its a's or b's? How does it produce strings such as aab or abb which have both the symbols?

Am I correct in understanding it as if the ( )* is repeated 3 times for example, it would give (a+bb)(a+bb)(a+bb). If the first () give a, second () gives b and third ( ) gives b, then it would essential be (a)(b)(b) = {abb}?

Could you give some example strings outputted when a regular expression has multiple Kleene closures within each other such as (a*ba*ba*)*? I don't understand how it can't produce the string {abababa}. Essentially repeating a* 1 time, the ba* 1 time and the other ba* 2 times (i.e concatenating the first ba with the second ba repeated twice). Having some examples would maybe help in understanding the way the strings are being combined and formed and if I am missing such as if the ba* is not supposed to be grouped together.

image text in transcribed

\begin{tabular}{|l|l|} \hline \multicolumn{1}{|c|}{ Regular Expression } & \multicolumn{1}{c|}{ Corresponding Regular Language } \\ \hlinea+bc & {a,bc} \\ \hlinea(b+c) & {ab,ac} \\ \hline(a+b)(a+c)(L+a) & {aa,ac,ba,bc,aaa,aca,baa,bca} \\ \hlinea(b+cc) & {b,cc,ab,acc,aab,aacc,aaab,aaacc,} \\ \hlinea+bb & {a,b,bb,bbb,bbbb,bbbbb,} \\ \hline a & {L,a,bb,aa,abb,bba,bbbb,aaa,} \\ \hlineab & {L,a,b,aa,ab,bb,aaa,aab,abb,bbb,} \\ \hline \end{tabular}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Students also viewed these Databases questions