Assignment 2 - Question 3

Just want some clarification on how everyone interpreted the question - does it mean it will only accept words that ONLY contain an even number of 'ab' substring, but no other letters (eg: abab, abababab) or can the word contain other letters as well, but as long as has even number of 'ab' substrings (eg: abaab, abababbab)?

Thanks in advance.

It means that the FA will accept all words that contain an even number of occurrences of the ab-substring. Thus, your second interpretation is correct.

Through a spanner in the works and ensure that the FA (or machine) does not leave it's Final state should one or more a's or one or more b's be receieved after the last even numbered 'ab' substring, but msut also leave the Final state should another 'ab' substring (count now odd) be received.

In some sick kind of way, I actually enjoyed this section. Which was a little surprising after the Recursion + Induction section.

Sorry - Maybe "throw a spanner in the works" might be a little easier.

Ok I must be losing it... looking at the solutions for exam purposes does not make sense to me because the first ± state on the left has a 'b' loop and 'b' on its own is NOT 'ab' so this word IS accepted and should not be?!

What am I missing?

Donald.

This one confuses me too.

From the solution, it seems that 0 is considered an even number. By that I mean a and b and ba are accepted words.

So, if the word has no occurance of the substring ab or an even number of occurances of the substring ab, it is accepted.

Does this sound right?

These questions worry me because there is more than one interpretation of the question...

The machine will accept any word with any number of a's and any number of b's, but if the word contains the substring ab then it will only accept it if there are an even number of them. It's not saying it will exclusively accept only ab's and only an even number of them....and yes it will accept the null word too given by the combination start and final state ie +-.

aaaaaaaaaaaaaaabaaaaaaaaaaababbbbbbbbbbbb is a word in this language...there are 2 substrings ab.

aaaaaaaaaaaa
bbbbbbbb
b
a
bbbbbbbaaaaa
ba

are also words in this language

BTW 0 is an even number, but that is irrelevant in this case.

Clive

Thanks Clive - that makes sense.

Donald.