logo Use CA10RAM to get 10%* Discount.
Order Nowlogo
(5/5)

DFA deterministic finite-state automaton

INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS

The following abbreviations are used in this paper.

DFA deterministic finite-state automaton

NDFA non-deterministic finite-state automaton

FSA finite-state automaton (either DFA or NDFA) NPDA non-deterministic pushdown stack automaton CFG context-free grammar

ID instantaneous description

TM Turing machine

1 (5 marks)

State the five components of the NDFA given below:

2 (10 marks)

Using a systematic procedure, convert the following NDFA into an equivalent DFA, and draw the resulting automaton. Show clearly all the steps involved.

3 (10 marks)

By constructing a tree, identify the distinguishable states for the DFA below. Hence draw a DFA which is equivalent to this one, but which has a minimal number of states. Note that this DFA is complete; you should ensure that your answer is also a complete DFA.

4 (5 marks)

Consider the DFA in Question 3 and convert it into a regular expression using a systematic procedure. [Hint: It may be easier to calculate the regular expression for the minimal DFA.]

5 (5 marks)

The company you are working for has a number of systems that exchange information in binary format. The company wishes to add a primitive error-detection scheme where prior to communicating a binary string, a system must attach either a 0 or a 1 to the end of the original string according to the following conditions:

The value attached is 0 if the number of 0s in the original string is greater than the number of 1s.

The value attached is 1 otherwise; that is if the number of 1s is greater than or equal to the number of 0s.

Your manager has asked you to implement a DFA that checks whether a binary string received by a system contains an error or not.

Your task here is to either produce such a DFA or prove to your boss that a DFA cannot be created to solve the task.

[Hint 1: If it is easier, you may first construct an NDFA and then convert it into a DFA.]

[Hint 2: You may use the pumping lemma to prove that the language is not regular, and therefore no DFA can be created.]

 6 (5 marks)

Now, the company has decided to modify the error-detection schema. Prior to communicating a binary string, a system now must attach either a 0 or a 1 to the end of the original string according to the following conditions:

The value attached is 0 if the number of 1s in the original string is even;

The value attached is 1 otherwise; that is if the number of 1s in the original string is odd.

Your manager has asked you to implement a DFA that checks whether a binary string received by a system contains an error or not.

Your task here is to either produce such a DFA or prove to your boss that a DFA cannot be created to solve the task.

[Hint 1: If it is easier, you may first construct an NDFA and then convert it into a DFA.]

[Hint 2: You may use the pumping lemma to prove that the language is not regular, and therefore no DFA can be created.]

 

(5/5)
Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Atharva PatilComputer science

883 Answers

Hire Me
expert
Chrisantus MakokhaComputer science

745 Answers

Hire Me
expert
AyooluwaEducation

783 Answers

Hire Me
expert
RIZWANAMathematics

796 Answers

Hire Me

Get Free Quote!

418 Experts Online