Cohen Chapter 5 Problem 2: Question Semantics

Hi

I'm going to raise the issue with a lecture as-well but I just want your guys input on the semantics of Problem 2:

"Build an FA that accepts only the language of all words with b as the second letter."

I interpret the question as b my only appear once in a word as the second letter of the word.

Because with the solutions given in the study guide I feel the question should been stated as follow:

"Build an FA that accepts only the language of all words with b as a second letter."

But most probably it is just me reading in to much into a question, or not

Very good question...I agree with your logic. They can't really deduct marks if we did it in another way, since there is no way to say that it would be wrong.

_______________________________________
Don't be different...be the one making a difference

Thanks for the feedback BlaXpydo!

After working out more solutions I realized: If we get such a open question I will just clearly state in my answer what I believe the question mean, and then solve the question using the assumptions I made.

So I'm sure if I fail and ask to review my exam paper I can fight them for the extra marks to pass

Um ... How many second letters does eg. your name have?

(The observation is just a tad out of time, I'll grant you).

Hi eddy

I do believe you are misinterpreting my question. I'm asking if the above question states that b my only appear once in a word generated by a FA. So lets use your name as a example "eddy" it consist out of the following alphabet {e, d, y}. How I interpret the question was that d may only occur once in a word thus your name with double d letters would not be accepted by the FA .

But I contacted the lecture and she told me: No, they will clearly state in the question how many times a certain letter may appear in a word so my semantic rambling is not correct in this case. But this is a classic case of interpretation and why things should be formally defined.

For example, I which they would ask the question like a formal definition:

Build in FA that adhere to the following rules:

1 The FA will only contain letters of the alphabet {a, b}.
2. b must be the second letter of all the words that is accepted by the FA.
3. Only words that adhere to the above to rule can be accepted by the FA.

Regards,

Wouldn't it just be something like (a+b) b (a+b)* ?

You pick one single first letter from the first parentheses (because that + forces you to choose one, only), and then you can only move right to the second letter of the word, because there's no asterisk. Here your sole option is a b. Thereafter you keep running round like a hamster on a treadmill inside the final parenthesis, picking either an a or a b each time. Or you say "Sod this, I've had enough of this word, and you terminate with a Lambda".

The word has just one first letter, one second letter, etc. (This property is essential to the existence of sequences of all sorts).

If you say b must be "a" second letter, you're implying that there's some choice in the matter. b is one of the available second letters. This is probably a point to let go of. It all boils down to what the conventions of English are, and might distract you from the business of tangling with the mathematics. I suppose that's a risk when the study material uses English instead of symbolic language.

I would interpret it as follows:

"Build an FA that accepts only the language of all words with b as the second letter."

this includes the following words:

ab, bb, aba, abb, abaa, abab, abba, abbb ...

it does not include the words:

^, a, b, aa, ba, aaa, aab, baa, bab, ...

what a crap subject. I cant see it being usefull for anything, ever. ag, just hope my doodling will get me enough marks to pass, so that I dont have to redo this shit.

@RandalFlag

Why don't you atleast try to understand the work? Won't you be taking Theoretical Computer Science 3 next year?

_______________________________________
Don't be different...be the one making a difference

no ways!

@RandallFlag, if you want to know what this subject is is used for, then you should have a look at computer language generation tools like http://www.antlr.org/.
These tools are used for generating compilers for programmable languages, and the theory that you learn in this subject gives a pretty good background to understanding whats going on inside such tools.

Have a look at the screenshot for the antlrWorks tool and you'll see a familiar Finite Automata.