A marker automaton (MA) is a deterministic 1-tape 1-head machine with input alphabet {0, 1}. The head can move left or right but is constrained to the input portion of the tape. The machine has the ability to write only one new character to a cell, namely #. (a) Give an example of language D that is accepted by an MA but is not context-free. Justify your answer. (b) Show that Kma = { hM, wi : M is an MA accepting w } is recursive.

See explaination

Explanation:

In our grammar for arithmetic expression, the start symbol is <expression>, so our initial string is:

<expression >

Using rule 5 we can choose to replace the nonterminal, producing the string:

<expression >*<expression >

We now have two nonterminals, to replace, we can apply rule three to the first nonterminal, producing the string:

<expression >+<expression>*<expression>

We can apply rule two to the remaining nonterminal, we get:

(number)+number*number

This is a valid arithmetic expression as generated by grammar.

Given a grammar G with start symbol S, if there is some sequence of production that when applied to the initial string S, result in the string s, then s is in L (G). the language of the grammar.