Scribd
Upload
10 views2 pages

Computing Theory Assignment Overview

This document outlines an individual assignment in computing theory. It consists of two parts: Part A requires students to design a non-deterministic finite automaton (NFA) that accepts binary strings with at most two zeros and at least two ones, including a state transition table and explanation. Part B asks students to construct a regular expression for the given NFA using state elimination, explaining each step and the rules applied. The deliverables are a documentation report in hard copy with specified sections, and a soft copy of the report file. Students are warned that all work must be their own or properly cited to avoid plagiarism charges.

Uploaded by

Yi Fan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
10 views2 pages

Computing Theory Assignment Overview

This document outlines an individual assignment in computing theory. It consists of two parts: Part A requires students to design a non-deterministic finite automaton (NFA) that accepts binary strings with at most two zeros and at least two ones, including a state transition table and explanation. Part B asks students to construct a regular expression for the given NFA using state elimination, explaining each step and the rules applied. The deliverables are a documentation report in hard copy with specified sections, and a soft copy of the report file. Students are warned that all work must be their own or properly cited to avoid plagiarism charges.

Uploaded by

Yi Fan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Computing Theory Individual Assignment Page 1 of 2

Computing Theory

Coursework

The coursework is 50% of the assessment for the module.

Learning Outcomes

1. Design automata and generate regular expressions for specified languages.


2. Design and analyse context-free grammars for specific syntactic rules.
3. Describe and Design Turing machines to accomplish specified computations
4. Explain and discuss complexity and decidability of problems

Assessment Criteria
IMPORTANT: This is an individual assignment, all submitted components must be
your own work or appropriately accredited.

Referencing Code

If you use design or ideas from external sources like book/ magazine/ internet/forum,
then proper citation should be done using the Harvard Name convention within your
solution. Failure to reference design/ideas properly is considered as plagiarism.

PART A: Non Deterministic Finite Automata

Design a Non- Deterministic Finite Automata that accepts ={0,1}. The Non-
Deterministic Finite Automata should be able to determine all strings that have at most
two zeroes and at least two ones. Construct the state transition table for the Automata.
Explain the correctness of the proposed Automata with sample strings that are accepted
and rejected by the State Machine.
Sample Data Accepted by the Automata :
101101
0111
11

Sample Data Rejected by the Automata :


1011010
01
0010

Asia Pacific University of Technology and Innovation 2017


Computing Theory Individual Assignment Page 2 of 2

PART B:

Construct a Regular Expression for the given NFA by using State Elimination
method. Provide proper explanation for each step mentioning the rules applied
for eliminating a state.

DELIVERABLES

You are required to submit:

Documentation (hardcopy)
1. Cover page
2. Table of contents
3. Introduction
4. Explanations :
Part A: State Transition Table, NFA diagram, List of acceptable inputs.
Part B: Step by Step evaluation of state elimination method including the
rules.
5. Conclusion
6. References

CD Content (softcopy)
1. Documentation report (.docx/.doc/.rtf)

Asia Pacific University of Technology and Innovation 2017

You might also like