Been working through the past exam papers. Does anyone have any memorandums so we can check if we are right?

J]]>

I'm working through the recommended examples, and have run into something strange.

Problem 12 i for chapter four asks you to say why two expressions are equivalent.

Now, the answer they give in the study guide doesn't quite make sense. As far as I can tell, you can construct the word "abbba" with the first expression, but not he second. Surely that means they aren't equivalent? As far as I understand it, if they are equivalent, they refer to the same language, meaning they have all the same words.

Am I missing something?]]>

I find FA's so elegant I decided I wanted to write a quick python script that can render it for me using Graphviz instead of studying and thus the following bit of code was born:

Source code

the above example will create the following transition diagram:

Graphviz Transition Diagram

Hopefully somebody else also finds it interesting.

If I have more time I would like to use the algorithms defined by Kleene to write it to a regex and back.

Later,]]>

I was just checking out the exam tutorial letter on Osprey, and I saw it's quite outdated. It seems to be for the Oct/Nov exam for 2009. Does anyone have a new one, or is the outline the same again?

J]]>

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

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

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

k

Now:

(k + 1)

> (2k + 1) + 2k + 1 // OK the next term in the sequence of RHS = 2k + 2 + 2k // um, simplifying RHS but, what happened to LHS? = 2(k + 1) + 2k // um, more simplifying RHS ... I think coz I don't see a power of 2. > 2(k + 1) + 1 // stumped! I don't know where this comes from...

foo]]>

Any help would be appreciated.

TIA

Mike]]>

My opinion, I felt it was too short a time. I didn't get a chance to finish all my questions.]]>

1. an FA not containg 'ba'?

2. an FA containing even number of substrings of 'ab'

appreciate your help]]>

I've done almost all of assignment 2, but question 1 still has me confused. In the module it seems we only work with numbers in these cases. For example on p. 13 of the study guide the additional exercises we are supposed to do the same as Assignment Question 1 but with numbers. This is easy enough. The function, for example, is something like f(x)=x+1. However, how are we supposed to write the function with the alphabet {a,b}? In question 1 a i have the generators aba,abb,aab and bab. How am I supposed to formulate a mathematical function from this? I mean, it's supposed to be odd strings containing "ab". So do I say f(x)=x+a*b* or f(x)=x+b*a* or what?

Could someone please help me out or at least point me to a similar example somewhere in the textbook or study guide.

Thanks]]>

Q2c) I cant seem to prove it -> I end up with trying to prove the following equation (everything following the ^ is the exponent, everything following the / is under the line)

here we can simplify the first part up to 1/2^k to something based on the induction principle

ie.

that means that we have to prove

either I am misunderstanding this, or making as dumb mistake, or I just cant do the algebra :-). any advice would be greatly appreciated.]]>

then ask, wish of the following words are in the language?

I cant seem to fit any of the options given..

Am I incorrect or is there something wrong with the question.

Many thanks]]>

Page 14 of the study guide: Sequences:

to me the recursive definition of a sequence should be the same as the definitions on the previous pages. let me explain:

EVEN is defined as: (2,4,6,8,...)

Universal set R

generator 2

function: f(x) = x+2

For the sequence (-1,2,5,3n-4)

Now my first thought was:

Universal Set Z (integers)

generator 1

function f(x) = 3x-4

However, obviously 1 isnt in the sequence, so it can tbe a generator. -1 is in the sequence though, and is seems to me I must now find the function that gets me to the next number in the sequence, so that I could use it in the recursive definition. Now the study guide tells me 1) I need a universal set of ZxZ (ie. ordered pairs). I dont understand why. I am thinking tht this is to specify the inputs to the function f as such (-1,1)(2,2)(3,5)(n,f(n)).. right? the next pair in this sequence should be (n+1,f(n)+3)

This simply concludes that F(N+1) would give F(n) + 3 (ie. The function with the next N would give the answer of function of the previous N + 3.

I talking a lot - perhaps the question here is: Are we using ordered pairs and the universal set of ZxZ ONLY because we need to explain the recursive definition in terms of functions with input/output? (because of not having a more simple generator and function)(in stead of having a single generator, now we have F(1) = -1 as the generator?)

Im afraid of misunderstanding something here..]]>

y

I understand that reverse(y

Any assistance would be appreciated.

Ronica]]>