2006 Q1

Question 1 (2006)

a) Well my attempt at the FA

Please read comment bellow by louisrdev. Agreed.



Now the translation:

S -> aM | bN
M -> aO | bO | /\ (a ending)
O -> aQ | bM
Q -> aO | bO

N -> aP | bP | /\ (b ending)
P -> bR | aN
R -> aP | bP

and of course it could be made tidy, but why waste the time. It does what it does. I think!

b)Convert

S -> Xa | Y
X -> aS | aY | bbb | bx
Y -> bY | /\ | a

to CNF

i) boot the /\

S -> Xa | Y
X -> aS | aY | bbb | bx
Y -> bY | b | a <-

ii) kill unit productions

S -> Xa | bY | b | a <-
X -> aS | aY | bbb | bX | a
Y -> bY | b | a

iii) Terminals

S -> XA | BY | b | a <-
X -> AS | AY | BBB | BX | a <-
Y -> BY | b | b <-
B -> b
A -> a

iv) No CNF

S -> XA | BY | b | a
X -> AS | AY | MB | BX | a <-
Y -> BY | b | a
M -> BB
B -> b
A -> a

I feel in your example Q and R should be your final states and not M and N. Making M and N your final states could cause the words 'a' and 'b' to be accepted, which strictly does not start and end with different characters,

Because of this you would also need to make the following changes:


S -> aM | bN
M -> aO | bO
O -> bQ | aM
Q -> aO | bO | /\ (a ending)

N -> aP | bP
P -> aR | bN
R -> aP | bP | /\ (b ending)

Other than that I think your solution is pretty accurate.

On the second part of the question, I agree completely.

Thanks for the contribution guys, really helping me!

I have another solution.
Is your M and N halt states? If so, then a and b are accepted respectively.
To me that is not in the language.

S -> aA | bB
B -> aY | bY
A -> aX | bX
Y -> aB | bB | a
X -> aA | bA | b

b)
One small thing.
Because Y is null, S is null, which enables X -> a when removing null.

_____________________________________
The sun is always shining, but it is far away.