Regular Expressions and Grammars

Question 1

Conider the following regular expression:

a ( a | ba )* b*

Conver the regular expression to an NFA using the NFA equivalents (concatenation, alternation, Kleene closure) of the regular expression operations. Show the steps in details.

Question 2

Consider the followig input alphabet:

E = {a,b}

Write regular expression for each fo the following strings:

a) Strings containing exactly two "a"
b) Strings containing at least two "a"
c) Strings containing at most two "a"
d)Strings ending with "a"
e)Strings starting and ending with the same symbol

Question 3

Consider the following grammar:

S -> aS | Sa | a

Is the grammar ambiguous? Explain with an example.