代写MATLAB Design a pushdown automata (PDA)

日期：2018-04-18 10:06

Design a pushdown automata (PDA)

1.Consider the language of all binary strings that start and end with the same symbol.

(a) Write the production rules of a grammar for this language. Show some derivations to test that your grammar is correct.

(b) Design a pushdown automata (PDA) to recognise this language. Give an implementation level description of your PDA. That is, explain what the machine will do in plain English.

(c) Draw a diagrammatic state machine model showing all the moves of your PDA.

(d) State carefully any assumptions you have made.

2.Consider the language of arithmetic expressions as a string of additions and/or subtractions of natural numbers. For example, 23 + 6 − 25 + 0 or 990 or 1 − 2 are valid expressions.

(a) Outline an implementation-level description of a Turing Machine to recognise this language. Remember that for an implementation-level description you do not have to give a formal specification of the machine’s moves, but only to explain the algorithm in plain English explaining the series of steps the machine would use for this calculation.

(b) Draw a diagrammatic state machine model showing all the moves of your Turing Machine.

(c) State carefully any assumptions you have made.