41080 Theory of Computing science
Assessment Task 1-Individual Programming
Assignment [Code]
Format: Program and short Report
Length: <500 Lines of code,3-4 pages for the report
Submission: Electronic via Ed.If you do not do the programming in Ed,make sure you upload and click the "mark"button.
Weighting: 20%
Type: Individual
Preamble
Finite automata are amongst the simplest useful computational models.Despite their limited power, many automated tasks can be understood as finite automaton operations—or more precisely,finite state transducers that produce output beyond simple accept/reject decisions.Event-driven systems (such as GUl event loops)are naturally expressed as finite automata,and digital electronics components often implement finite automata in hardware.
Lexical analysis presents a particularly important application.Whether in compiler design,data processing,or natural language processing,lexical analysers typically use finite automata to recognise token patterns in input streams.
This assignment introduces finite automata through practical implementation:you willbuild a lexical analyser for arithmetic expressions using finite automaton principles.
Your Task
This assignment consists in two components,a program and a report.
The Program(Weighting:70%)
You will implement a deterministic finite automaton that reads an arithmetic expression character-by- character and produces a sequence of tokens representing numbers and operators.Your program must explicitly represent state and process input one character at a time,following the finite automaton model.
The one permitted exception to the strict automaton model is maintaining a buffer to collect digits whilst building number tokens,as this is necessary for practical implementation.
Number Format:
·A string of digits,optionally followed by a decimal point and a non-empty string of digits
·If a decimal point is present,the digits before it must be "0"only
·Numbers starting with "O"are either just "0"or "0.[digits]"
Expression Format:
·A valid number is a valid expression
·Any valid expression,followed by an operator,followed by a valid number
·Operators: +, -, *, /
·Whitespace is permitted only between numbers and operators Error Handling: Your program must detect and report:
·Malformed numbers
·Invalid expression structure
Implementation: Use the provided skeleton code in Java, Python, C++, Ruby, Rust or Haskell. The analyse method should take a string and return a list of Token s. Alternative languages require prior approval from the subject coordinator
Reflection:
·What challenges or limitations did you encounter when translating theoretical concepts into working code?
·How do the practical requirements (such as token generation)extend beyond pure automaton theory?
Marking
Program marking is based on automated unit tests.Example tests will be provided,and you can run the full test suite by clicking the "Mark"button,which also registers your submission.
Critical Requirement: Your program must use an automaton-based approach(with only the permitted number buffer exception).Programs that do not follow the finite automaton model will receive zero marks regardless of functional correctness.