Design a binary finite state automaton to accept all strings

Assignment Help Theory of Computation
Reference no: EM131557751

You have been assigned your own individual codes for the letters A, B, C and also a "parity property".

You can obtain your codes and parity property by following the FSA codes and party property link below.

You are the central hub for a communication system. Messages come to you as sequences of As, Bs and Cs but coded in binary. Each such binary message is to be followed by a "check digit". This is a final 0 or 1 so that the entire binary message satisfies your parity property.

The parity properties are:

Even 0 The entire message (including the check digit) has an even number of 0's.
Odd 0 The entire message (including the check digit) has an odd number of 0's.
Even 1 The entire message (including the check digit) has an even number of 1's.
Odd 1 The entire message (including the check digit) has an odd number of 1's.

For example if your codes are A = 101, B = 1101, C = 001 and your parity property is Odd0, the message ABAC would get encoded as 10111011010011. The final character is the check digit. It is a '1' because we want an odd number of 0s. So 10111011010011 is valid, but 10111011010010 and 10111011011100 are not. Make sure you correctly understand this example before you go further. ABAC is 1011101101001. It has 5 0s, so it already has an odd number of 0s. We have to add a check digit to keep this number odd, so the check digit in this case is 1. If the parity property had been Even0 the check digit would have been 0.

Your task is to design a binary finite state automaton (FSA) to accept all strings that represent valid messages (for your particular codes and parity property) and reject all others. This FSA must be DETERMINISTIC, REDUCED and must be in STANDARD FORM.

This project is machine marked. You can submit your attempts as many times as you like and your submission will be marked immediately. You will obtain one of 4 responses:

  • Your machine does not work. It does not process the string "..." correctly. The string that your machine processes incorrectly may assist you in understanding why your machine does not work. (0 marks)
  • Your machine processes all strings correctly, but is not in reduced form. This means that your machine accepts precisely those messages that are valid, but has states which are equivalent. (5 marks)
  • Your machine processes all strings correctly. It is reduced but is not in standard form. This means that your machine accepts precisely those messages that are valid, has the right number of states, but they are not named in the correct order for standard form. (6 marks)
  • Your machine processes all strings correctly, and is in reduced standard form. Your machine is completely correct. (8 marks)

You should submit an answer once you think you have found a deterministic machine for your particular codes and parity property. If it is right, you will be told that it works but is not in reduced form. You can then reduce it, and check that you are still right so far. Once it is correctly reduced, you can then put it in standard form if necessary and submit that answer - hopefully finding that it is completely correct.

*The late penalty will reduce the mark for that submission by 1 mark for each day or part thereof after the deadline. Your best score counts. So, if you have a score of 6 out of 8 before the deadline, you can still improve that score to 7 out of 8 during the 24 hours after the deadline by making a submission that is completely correct.

Your individual codes and parity property are: A: 0001, B: 0101, C: 111, Parity: Odd 0

Reference no: EM131557751

Questions Cloud

Suppose you own a television factory : Suppose you own a television factory and at your current level of output you have average total cost of $800 per television, average variable costs
How many different ways can a student complete the exam : EXAMS An exam consists of ten true-or-false questions. Assuming that every question is answered, in how many different ways can a student complete the exam?
What is an ecological footprint : What is an Ecological Footprint? What were the results of your test and what, if anything, did you find surprising or noteworthy
Identification of warranty numbers : WARRANTY NUMBERS A warranty identification number for a certain product consists of a letter of the alphabet followed by a five-digit number.
Design a binary finite state automaton to accept all strings : Design a binary finite state automaton (FSA) to accept all strings that represent valid messages (for your particular codes and parity property) and reject all
Explore the companys decision to distribute a dividend : Briefly anlyze whether the company's first month of operations was a success. Explore the company's decision to distribute a dividend.
In how many ways can the first prizes be awarded : LOTTERIES In a state lottery, there are 15 finalists eligible for the Big Money Draw. In how many ways can the first, second, and third prizes be awarded.
Find the number of employed : Find the number of employed, labor force participation rate, and unemployment rate.
What is the historical significance of atzmaut and al-nakba : What was the mandate system and what impact did it have on Zionist-Palestinian relations? What is the historical significance of Atzmaut and al-Nakba

Reviews

Write a Review

Theory of Computation Questions & Answers

  Finite-state machine design

Create a finite-state machine design to turn your FPGA development board into a simple programmable music box.

  Redundant sequence identi cation

Redundant sequence identi cation

  Compute a shortest superstring

Dynamic programming algorithm to compute a shortest superstring.

  Propositional and predicate logic

Write down a structural induction principle for the PlayTree free type

  Design a syntactic analyzer

Design a syntactic analyzer for the language specified by the grammar

  Design unambiguous grammar to parse expressions

Write a program would read two numbers and then print all numbers between the first and the second, inclusive. Design unambiguous grammar to parse expressions

  Consider a logic function with three outputs

Consider a logic function with three outputs,  A ,  B , and  C , and three inputs,  D ,  E , and  F . The function is defined as follows:  A  is true if at least one input is true,  B  is true

  Considering a single programmed operating system

Considering a single programmed operating system, what is the minimal total time required to complete executions of the two processes? You should explain your answer with a diagram.

  How to construct an nfa

Give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L).

  Equivalence classes to construct minimal dfa for language

How many equivalence classes does this relation have and what are they? Use these equivalence classes to construct the minimal DFA for the language.

  Impact of moore-s law on data center costs

Discuss the impact of Moore's law on data center costs on such things as servers and communications equipment. List at least 3 steps or recommendations your data center can take to offset some or all of the effect of Moore's law.

  Problem encountered in statements in predicate logic

How the problem would be encountered in attempting to represent the following statements in Predicate logic. it should be possible to: John only likes to see French movies.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd