Explore BrainMass

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 already-completed solution here!

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

L = {AnBnCn : n>=1}

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 October 24, 2018, 8:47 pm ad1c9bdddf

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.

See Also This Related BrainMass Solution


Let  be a 3cnf-formula. An  assignment to the variables of  is one where each clause contains two literals with unequal truth values. In other words an  -assignment satisfies  without assigning three true literals in any clause.

a. Show that the negation of any -assignment to  is also an -assignment.
b. Let SAT be the collection of 3cnf-formulas that have an -assignment. Show that we obtain a polynomial time reduction from 3SAT to SAT by replacing each clause cI

(y1 V y2 V y3)

by the two clauses

(y1 V y2 V zI) and ( V y3 V b)

where zI is a new variable for each clause cI and b is a single additional new variable.
c. Conclude that SAT is NP-complete

See attached file for full problem description.

View Full Posting Details