FIT2014 Theory of Computation


Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


FIT2014 Assignment 1 Linux tools, logic, regular expressions, induction (Week 4)

Start work on this assignment early. Bring questions to Consultation and/or the Ed Forum. 

Instructions

  • Generative AI tools must not be used for any part of this Assignment. You must not use generative artificial intelligence (AI) to generate any materials or content in relation to this Assignment (or any other assessment in this unit). For example, no GPT, DeepSeek, Copilot, Claude, Cohere, Gemini/Bard, etc.
  • The work you submit for this Assignment must be your own individual work.
  • To start work, download the workbench asgn1.zip from Moodle. Create a new Ed Workspace and upload this file, letting Ed automatically extract it. Edit the student-id file to contain your name and student ID. Refer to Lab 0 for a reminder on how to do these tasks.
  • The workbench provides names for all solution files. These will be empty, needing replacement. Do not add or remove files from the workbench.
  • Solutions to written questions must be submitted as PDF documents. You can create a PDF file by scanning your legible (use a pen, write carefully, etc.) hand-written solutions, or by directly typing up your solutions on a computer. If you type your solutions, be sure to create a PDF file. There will be a penalty if you submit any other file format (such as a Word document). Refer to Lab 0 for a reminder on how to upload your PDF to the Ed workspace and replace the placeholder that was supplied with the workbench.
  • Every PDF file submitted must also contain your name and student ID at the start.
  • When you have finished your work, download the Ed workspace as a zip file by clicking on “Download All” in the file manager panel. You must submit this zip file to Moodle by the deadline given above.
  • To aid the marking process, you must adhere to all naming conventions that appear in the assignment materials, including files, directories, code, and mathematics. Not doing so will cause your submission to incur a one-day late-penalty (in addition to any other late-penalties you might have). Be sure to check your work carefully. 
  • Your submission must include:
  • the file student-id, edited to contain your name and student ID;
  • a text file, prob1a.txt, with your solution to Problem 1(a);
  • another text file, prob1b.txt, with your solution to Problem 1(b);
  • another one-line text file, prob2.txt, with your awk pattern for cell lines in Problem 2;
  • an awk script, prob2.awk, for Problem 2;
  • a PDF file prob3.pdf with your solution to Problem 3;
  • an awk script, prob4.awk, for Problem 4;
  • a file prob5.pdf with your solution to Problem 5.

Initially, the asgn1 directory contains empty files (or dummy files) with the required filenames.

These must each be replaced by the files you write, as described above. Before submission, check that each of these empty files is, indeed, replaced by your own file, and that the student-id file is edited as required.

Importantly, you must ensure that the filenames you submit match those listed above, and that no other files are included although any directory or filename beginning with a period ‘.’ or underscore ‘_’ will be ignored.

Introduction to the Assignment

In Lab 0, you met the stream editor sed, which detects and replaces certain types of patterns in text, processing one line at a time. These patterns are actually specified by regular expressions.

In this assignment, you will use awk which does some similar things and a lot more. It is a simple programming language that is widely used in Unix/Linux systems and also uses regular expressions.

In Problems 1–4, you will construct an awk program that builds, for an instance of grid navigation problem, a Boolean expression in Conjunctive Normal Form (CNF). That CNF will capture the existence of a joint path for the agents in the grid to reach their goals in a given number of steps while respecting the movement rules and safety constraints.

Finally, Problem 5 is about applying induction to a problem related to the structure and satisfi- ability of some Boolean expressions in Conjunctive Normal Form (CNF) constructed when solving Problems 1–4.

2026-04-01