Question

find the set notation for the following regular expression: L(aa*(ab+a)*). build its corresponding automaton. find a regular grammar for it.

Answer 1

Solution :

Set notation :

aa*(ab+a)*

Regular grammer :

G = (V, T, S, P), where

V = {S, A, B},

T = {a, b},

P = {S $\rightarrow$ aA; A $\rightarrow$ aA|aB| $\lambda$ ; B $\rightarrow$ bA}

The derivation of a string aaaababa :

S $\Rightarrow$ aA $\Rightarrow$ aaA $\Rightarrow$ aaaA $\Rightarrow$ aaaaB $\Rightarrow$ aaaabA $\Rightarrow$ aaaabaB

   $\Rightarrow$ aaaababA $\Rightarrow$ aaaababaA $\Rightarrow$ aaaababa.