My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
October 3rd, 2014, 11:40 PM   #1
Joined: Oct 2014
From: italy

Posts: 1
Thanks: 0

Partial functions modelled by Labelled Transition Systems

Hi there! I'm new in this forum and I'm looking for an help to solve an exercise from my Formal Languages' Course at the university...

I'll write down the assignment and then I'll ask some questions...

Let Q be the set of partial functions from integers to integers. In symbols, Q={ f | f:Z->Z U{undefined} }, where f(x)= undefined models the fact that the function f is undefined on x. Let S = (Q, ZxZ, ->, {f0}), where f0(x)=undefined for all x belonging to Z, and the transition relation is defined by the following rule:
IF ( f(x)=undefined ) THEN ( f(x,v) --> f{v/x} )
WHERE : f {v/x}(y)=v if x=y, OR f{v/x}(y)=f(y) otherwise.
Describe informally the set of traces of S. Does S have infinite traces? What is the cardinality of Q? Is it true that any machine for S would require an infinite amount of space to represent the state of S?

I know that what I've written is very clumbsy... Sorry for that...

The first thing I need to understand is the meaning of the {} notation, why do we use f{something}(sth) and what are we modelling?

The other thing I didn't catch is whether there are transitions or not: if f0 is the initial state BUT it is always undefined (for all x in Z) then we'll never move from this state to another one... Isn't this correct?

Please HELP ME... I'm stubbornly looking at this exercise from days and days without any idea...

What I need is at least a small clue!!!!

Byeee (and sorry for my bad english!!! )

Last edited by akil78; October 3rd, 2014 at 11:45 PM.
akil78 is offline  

  My Math Forum > Science Forums > Computer Science

functions, labelled, modelled, partial, systems, transition

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
minimization operator for partial recursive functions safyras Calculus 1 April 21st, 2014 10:27 AM
Extrema of multivariable functions - systems of equations Akcope Calculus 5 March 8th, 2014 11:28 AM
Has anyone ever modelled the Global Economy? redmotion Economics 1 November 12th, 2013 08:56 AM
Graph Theory - Simple Labelled Graphs Jet1045 Applied Math 5 May 16th, 2013 10:09 PM
Partial recursive functions twoflower Applied Math 0 December 22nd, 2007 01:47 AM

Copyright © 2019 My Math Forum. All rights reserved.