Examen 3 Automata

Question 1

Is every Turing-recognizable language decidable?

Answer 1

False

Question 2

If there exists a language L, for which there exists a Turing Machine T that accepts every word in L and either rejects or loops for every word not in L, what is it called?

Answer 2

Recursively enumerable

Question 3

In the context of a Turing machine, which of the following is the transition function?

Answer 3

a) δ: Q × Γ → Q × Γ × {L, R}

Question 4

A Turing machine is defined as a 7-tuple. What does Σ represent?

Answer 4

c) The input alphabet not containing the blank symbol

Question 5

Which of the following statements is FALSE?

Answer 5

b) A language is decidable if and only if it is Turing recognizable

Question 6

In a Turing machine, can the read–write head move only to the right?

Answer 6

False

Question 7

Can a problem be solved by an algorithm if and only if it can be solved by a Turing Machine?

Answer 7

True

Question 8

In a multi-tape Turing machine, can it be transformed into a single-tape Turing machine?

Answer 8

True

Question 9

Which of the following statements is FALSE?

Answer 9

a) The special states for rejecting and accepting take effect after reading new symbols in the tape.

Question 10

Do there exist languages that are decidable but not Turing-recognizable?

Answer 10

False

Question 11

A nondeterministic Turning machine is a decider, if all branches halt on all inputs

Answer 11

True

Question 12

A turning machine have a finite tape to storage symbols

Answer 12

False

Question 12

Turing machine(TM) is more powerful than FSM because

Answer 12

It has the capability to remember long sequences of input symbols

Question 13

Which of the following is a Turing machine with an attached printer

Answer 13

Enumerator

Question 13

A Turing machine is a 7 tuple T = Q , signme , T , S, q, q, ) Where

Answer 13

Qrecect E Q is the reject state, where Qreject != Qaccept