Explore BrainMass
Share

Turing machine to accept the language "A^n B^n C^n"

This content was STOLEN from BrainMass.com - View the original, and get the solution, here!

Give the transitions for a turing machine that accepts the language given below.

L = {AnBnCn : n>=1}

Where,
An denotes a raised to the power n (a^n)
Bn denotes b raised to the power n (b^n)
Cn denotes c raised to the power n (c^n)

© BrainMass Inc. brainmass.com September 24, 2018, 10:14 am ad1c9bdddf - https://brainmass.com/computer-science/theoretical-computer-science/turing-machine-to-accept-the-language-a-n-b-n-c-n-107765

Solution Preview

Notations used for denoting a turing machine transition are as follows.

(StartState, SymbolRead) --> (EndState, SymbolWritten, MovementDirection)

* Movement Directions are denoted by R (right) and L (left).
* E is used to denote NULL symbol (or absense of symbol in a tape cell).
* $ denotes a marker ...

Solution Summary

Apart from the transitions list for the turing machine, solution also provides stepwise guidance on how to construct a graphical representation for it.

$2.19