Complete the sentence. All of the following are terms defining type 0 grammar EXCEPT:

Choose one answer.

	a. A symbol called the middle.
	b. Alphabet, whose elements are called non-terminal symbols.
	c. Production rules.
	d. Alphabet disjoint from non-terminal symbols, whose elements are called terminal symbols.

Question 2

Each context-free language is also what type of language?

Choose one answer.

	a. Type 1 language
	b. Type 2 language
	c. Type 3 language
	d. Type 4 language

Question 3

Fill in the blank. A set is a regular set only if it is accepted by a _______________.

Choose one answer.

	a. Finite-state automaton.
	b. Infinite-state automaton
	c. Semi-finite-state automaton
	d. Cellular automaton

Question 4

Fill in the blank. An accepting computation of a pushdown transducer is a sequence of moves that starts at an initial configuration and ends at a(n) _______________ configuration.

Choose one answer.

	a. Rejecting
	b. Monotone
	c. Accepting
	d. Probabilistic

Question 5

Fill in the blank. If a language is accepted by a finite-state automaton, then it is also decided by a _________________ finite-state automaton that has no epsilon transition rules.

Choose one answer.

	a. Non-deterministic
	b. Deterministic
	c. Half-deterministic
	d. Semi-deterministic

Question 6

Finite-state automata accept only what type of languages?

Choose one answer.

	a. Type 1 languages
	b. Type 2 languages
	c. Type 3 languages
	d. Type 4 languages

Question 7

Grammars do which of the following?

Choose one answer.

	a. Generate rules by modifying given strings.
	b. Generate functions with strings as inputs.
	c. Generate languages by repeatedly modifying given strings.
	d. All of the above

Question 8

How can sentential forms in type 0 grammar be displayed?

Choose one answer.

	a. By derivation qubits
	b. By derivation graphs, which are ordered, acyclic, directed, and labeled
	c. By tree graphs
	d. None of the above

Question 9

How many extra conditions does type 1 grammar have to satisfy in addition to the conditions that type 0 grammar satisfies?

Choose one answer.

	a. 2
	b. 1
	c. 3
	d. 4

Question 10

How many types of grammars are there?

Choose one answer.

	a. 2
	b. 3
	c. 4
	d. None of the above

Question 11

What are pushdown transducers whose output components are ignored called?

Choose one answer.

	a. Ignoring automata
	b. Cellular automata
	c. Ignoring machines
	d. Pushdown automata

Question 12

What is a deterministic machine?

Choose one answer.

	a. It is a physical process whose law of motion implements a rule that defines each output qubit in terms of the input quibits.
	b. It is a machine in which each state fully determines whether an input symbol is to be read and fully determines the transition rule to be used.
	c. It is a machine that is unbreakable.
	d. It is a machine that never stops working.

Question 13

What is a halting computation?

Choose one answer.

	a. A computation that occasionally halts
	b. A computation with infinite input length
	c. Any computation
	d. A computation that consists of a finite number of moves

Question 14

What is a pushdown transducer?

Choose one answer.

	a. It is an abstract computing machine that consists of a finite-state control, an input tape, a read-only input head, a pushdown tape or pushdown store, a read-write pushdown head, an output tape, and a write-only output head.
	b. It is a finite, nonempty ordered set with elements that are symbols or characters.
	c. It is the mapping of objects into strings in accordance with some rules.
	d. None of the above

Question 15

What is a string?

Choose one answer.

	a. An infinite sequence of symbols from a given alphabet
	b. A finite sequence of symbols from a given alphabet
	c. A set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head
	d. None of the above

Question 16

What is representation of information?

Choose one answer.

	a. It is a set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head.
	b. It is a physical process whose law of motion implements a rule that defines each output qubit in terms of the input quibits.
	c. It is the mapping of objects into random strings.
	d. It is the mapping of objects into strings in accordance with some rules.

Question 17

What is the definition of a finite-state automaton?

Choose one answer.

	a. It is a finite, nonempty ordered set with elements that are symbols or characters.
	b. It is the mapping of objects into strings in accordance with some rules.
	c. It is a tuple <Q, S, d, q, F>, where Q, S, q, and F are defined as for finite-state transducers, and the transition is a relation from Q x (S U {epsilon}) to Q.
	d. None of the above

Question 18

What is the most frequently used criteria to compare strings?

Choose one answer.

	a. The one that compares them by length.
	b. The one that compares them alphabetically.
	c. The one that compares them chronologically.
	d. The one that compares them by frequency of use.

Question 19

Which of the following conditions must hold true for a computation to be non-accepting?

Choose one answer.

	a. The sequence starts from the initial configuration.
	b. If the sequence is finite, then it ends at a configuration from which no move is possible.
	c. There is no accepting computation on given input.
	d. All of the above

Question 20

Which of the following conditions must hold true for a non-accepting computation of a pushdown transducer?

Choose one answer.

	a. The sequence starts from the initial configuration on given input.
	b. If the sequence is finite, it ends at a configuration from which no move is possible.
	c. There is no accepting computation on input.
	d. All of the above

Question 21

Which of the following is NOT part of the definition of a finite-state transducer?

Choose one answer.

	a. Non-deterministic symbols
	b. Input alphabet
	c. Output alphabet
	d. Finite set of states

Question 22

Which of the following is NOT part of the definition of a computing machine?

Choose one answer.

	a. Finite-state control
	b. Input tape
	c. Continuous function
	d. Output tape

Question 23

Which type of program accepts context-free language?

Choose one answer.

	a. Recursive semi-finite-domain program
	b. Recursive non-finite-domain program
	c. Non-recursive finite-domain program
	d. Recursive finite-domain program

Question 24

What is the best description of an alphabet?

Choose one answer.

	a. A set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head
	b. An infinite, nonempty ordered set with elements that are symbols or characters
	c. A finite, nonempty ordered set with elements that are symbols or characters
	d. None of the above

Question 25

How do covalent bonds get broken and formed under thermodynamic control?

Choose one answer.

	a. By a reversible reaction
	b. By an irreversible reaction
	c. By an intractable reaction
	d. By a deterministic action

Question 26

What are the four DNA nucleotides?

Choose one answer.

	a. Adenine, guanine, cytosine, and thiamine
	b. Adrenaline, guanine, cytosine, and thymine
	c. Adenine, guanine, cytosine, and thymine
	d. None of the above

Question 27

What are the good points of DNA computing?

Choose one answer.

	a. High parallelism
	b. High speed
	c. Energy efficiency
	d. All of the above

Question 28

What do biochemical computers depend on to achieve computational functionality?

Choose one answer.

	a. They depend on biological equations.
	b. They depend on biological cell interactions.
	c. They depend on biological chemical reactions.
	d. They depend on biological organisms.

Question 29

What do biocomputers depend on when they perform computations?

Choose one answer.

	a. They depend on biologically derived molecules.
	b. They depend on biologically derived cells.
	c. They depend on biologically derived organisms.
	d. They depend on biologically inspired equations.

Question 30

What do we call machines that manipulate molecular assemblies to perform movement, switching, and entrapment?

Choose one answer.

	a. Organic machines
	b. Cell machines
	c. Biological machines
	d. Molecular machines

Question 31

What is a phenomenon in which we construct a system without guidance from an outside source?

Choose one answer.

	a. Organism assembly
	b. Cell assembly
	c. Molecular self-assembly
	d. Artificial construction

Question 32

What is a phenomenon in which we design molecules to form a host-guest complex?

Choose one answer.

	a. Molecular recognition
	b. Cell recognition
	c. DNA recognition
	d. Organism recognition

Question 33

What is the name of the molecular architecture in which molecular structures depend on their topology?

Choose one answer.

	a. Gibbs's molecular architecture
	b. Turing's molecular architecture
	c. Markov's molecular architecture
	d. Mechanically-interlocked molecular architecture

Question 34

What is the name of the process in which a host of small molecules uses a suitable molecular species as a template?

Choose one answer.

	a. Markov's imprinting
	b. Molecular imprinting
	c. Cell imprinting
	d. Organism imprinting

Question 35

What kind of chemistry goes beyond the molecules and focuses on the chemical system and its assembled molecular subunits?

Choose one answer.

	a. Supramolecular chemistry
	b. Natural chemistry
	c. Nano chemistry
	d. DNA

Question 36

What operations are usually performed on DNA sequences?

Choose one answer.

	a. Synthesis and separation
	b. Merging and extraction
	c. Amplification and cutting
	d. All of the above

Question 37

What to bioelectrical computers depend on to perform computation?

Choose one answer.

	a. They depend on designed cells that conduct electricity.
	b. They depend on designed biomolecules that conduct electricity.
	c. They depend on designed organisms that conduct electricity.
	d. They depend on designed artificial cells that conduct electricity.

Question 38

Which famous problem would require tons of DNA to be computed by DNA computing paradigm?

Choose one answer.

	a. City search problem
	b. Turing's maximal efficiency problem
	c. Markov's minimal search problem
	d. Adleman's Hamiltonian path problem

Question 39

Which of the following most accurately describes the Hamiltonian path problem?

Choose one answer.

	a. Given a set of n cities connected by one-way and two-way roads, starting at the first city and ending at the last city, does a path through this network exist?
	b. Given a set of n cities connected by one-way and two-way roads, does a path through this network, starting at the first city and ending at the last city such that each city is visited once and only once, exist?
	c. Given a set of n cities connected by one-way and two-way roads, starting at the first city and ending at the last city such that each city is visited at least once, does a path through this network exist?
	d. None of the above

Question 40

Who first suggested a biochemical computing scheme to perform logical operations?

Choose one answer.

	a. James Clark
	b. Tom Knight
	c. Alan Turing
	d. Vladimir Nikiforov

Question 41

Why is it economically beneficial to use biocomputers?

Choose one answer.

	a. Because they build upon each other inexpensively
	b. Because they reorganize their structure inexpensively
	c. Because they self-replicate and self-assemble inexpensively
	d. Because they reproduce inexpensively

Question 42

What is DNA?

Choose one answer.

	a. It is deoxyribonucleic acid that encodes the genetic information of cellular organisms.
	b. It is an ordered sequence of acid molecules.
	c. It is the paradigm by which one computes using proteins.
	d. None of the above

Question 43

According to Rennard, what is the scaling problem in genetic algorithms?

Choose one answer.

	a. Differences between fitness are minimized through the genetic algorithm
	b. Population converges towards super-subject genome
	c. Reduced diversity of the genetic pool
	d. All of the above

Question 44

How are genetic algorithms different from classical optimization algorithms?

Choose one answer.

	a. They work on a population of points, not a unique one.
	b. They use the values of the function to optimize, not their derived function or other auxiliary knowledge.
	c. They use probabilistic transition function not determinist ones.
	d. All of the above

Question 45

What is a collection of chromosomes that evolve as an evolutionary algorithm progresses called?

Choose one answer.

	a. A colony
	b. An aggregate
	c. A population
	d. A group

Question 46

What is a common procedure in which a neural network searches for the optimal solution?

Choose one answer.

	a. Markov chain procedure
	b. Special procedure
	c. Error minimizing procedure
	d. Phase transition

Question 47

What is an elementary unit of a genetic algorithm that carries the information about the set of parameters representing a particular instance of a discriminant function called?

Choose one answer.

	a. Gene unit
	b. A basic unit
	c. A cell
	d. A chromosome

Question 48

What is the common learning method in neural networks that adjust the parameters in order to minimize the error function?

Choose one answer.

	a. Integrity back-propagation
	b. Hash back-propagation
	c. Error forward-propagation
	d. Error back-propagation

Question 49

What is the difference between patterns and classes?

Choose one answer.

	a. Patterns are functions in d-dimensional space, and classes are their sub-functions.
	b. Patterns are points in 2-dimensional space, and classes are sub-spaces in 3-dimensional space.
	c. Patterns are points in d-dimensional space, and classes are sub-spaces.
	d. None of the above

Question 50

Which algorithms are generally used for optimization and as a classification problem?

Choose one answer.

	a. Sub-string search algorithms
	b. Genetic algorithms
	c. DNA algorithms
	d. Biological algorithms

Question 51

Which method applies a linear transformation to each fitness, so the strongest subjects are appropriately influenced?

Choose one answer.

	a. Exponential method
	b. Windowing method
	c. Linear transformation method
	d. Linear normalization method

Question 52

Which method does reduce the fitness function of the worse subject to palliate scaling problem?

Choose one answer.

	a. Exponential method
	b. Windowing method
	c. Linear transformation method
	d. Linear normalization method

Question 53

Which method is effective due to consideration of mutation and genetic recombination?

Choose one answer.

	a. Markov method
	b. Knight method
	c. Turing method
	d. Holland method

Question 54

Which method is linearized to reduce the influence of the strongest subjects?

Choose one answer.

	a. Exponential method
	b. Linear normalization method
	c. Linear transformation method
	d. Windowing method

Question 55

Which method takes the square roots of the fitness plus one to reduce the influence of the strongest subjects?

Choose one answer.

	a. Exponential method
	b. Windowing method
	c. Linear transformation method
	d. Linear normalization method

Question 56

Which observation is the basis of genetic algorithms?

Choose one answer.

	a. Markov mechanism
	b. Turing mechanism
	c. Darwinian evolution
	d. Holland mechanism

Question 57

Which of the following best describes a classification problem?

Choose one answer.

	a. It deals with merging populations.
	b. It deals with finding the probabilistic transition function.
	c. It deals with associating a given input pattern with one of the distinct classes.
	d. All of the above

Question 58

Which of the following is NOT one of the principles of genetic algorithms?

Choose one answer.

	a. Encoding of the problem in a binary string
	b. Random generation of a population
	c. Reckoning of a fitness value for each subject
	d. Genomes stabilization

Question 59

Who is John Holland?

Choose one answer.

	a. A scientist who began work on a physical process whose law of motion implements a rule that defines each output qubit in terms of the input quibits
	b. A scientist who began his work on string algorithms at the beginning of the 60s and who first achieved the publication of String Searches in 1975
	c. A scientist who began his work on genetic algorithms at the beginning of the 60s and who first achieved the publication of Adaptation in Natural and Artificial System in 1975
	d. A scientist who worked on quantum computers and quantum physics

Question 60

According to Stephen Wolfram, what is the definition of a one dimensional cellular automaton?

Choose one answer.

	a. It is a physical process whose law of motion implements a rule that defines each output qubit in terms of the input quibits.
	b. It is a system of sites having a finite set of possible values, which are updated in discrete time steps according to a deterministic rule.
	c. It is a set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head.
	d. It is the mapping of objects into strings in accordance with some rules.

Question 61

According to Stephen Wolfram, which classes of cellular automata are characterized by spatial entropies that tend to zero with time?

Choose one answer.

	a. Class 2
	b. Class 1
	c. Class 3
	d. Class 4

Question 62

According to Stephen Wolfram, which classes of cellular automata generate sets of configurations with nonzero limiting spatial entropy?

Choose one answer.

	a. Class 1, 2 and 3
	b. Class 1, 2 and 4
	c. Class 1, 3 and 4
	d. Class 2, 3 and 4

Question 63

Given the rules for Wolfram's 1-D cellular automaton 111->0, 110->0, 101->0, 100->1, 011->1, 010->1, 001->1, 000->0 and initial state 010, how many 1's are in the row after 5 steps?

Choose one answer.

	a. 9
	b. 8
	c. 10
	d. 11

Question 64

Given the rules for Wolfram's 1-D cellular automaton 111->0, 110->1, 101->1, 100->0, 011->0, 010->1, 001->1, 000->0 and initial state 010, how many 1's are in the row after 5 steps?

Choose one answer.

	a. 6
	b. 5
	c. 4
	d. 3

Question 65

What are some of Wolfram's four basic classes of behavior found in cellular automata?

Choose one answer.

	a. Classes that tend to a spatially homogeneous state
	b. Classes that yield a sequence of simple stable or periodic structures
	c. Classes that exhibit chaotic aperiodic behavior
	d. All of the above

Question 66

What are the possible boundary conditions in the standard two-dimensional model CNN?

Choose one answer.

	a. Fixed (or Dirichlet), if the value of the boundary cells is a prescribed constant
	b. Zero-flux (or Neumann), if the value of the boundary cells is the same as the edge cells
	c. Periodic (or toroidal), if the value of the boundary cells is the same as the edge cells on the opposite side
	d. All of the above

Question 67

What do we call the number of distinct symbol sequences generated by Wolfram's cellular automaton evolution, without regard to the probabilities with which they occur?

Choose one answer.

	a. The final state
	b. The mix
	c. The diversification
	d. The entropy

Question 68

What is a Cellular Wave Computer?

Choose one answer.

	a. It is a set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head.
	b. It is a type of the Cellular Neural Network, based on the ﬂows and solutions of differential equations.
	c. A finite, nonempty ordered set with elements that are symbols or characters.
	d. None of the above

Question 69

What is Cellular Neural Network?

Choose one answer.

	a. It is a set of dynamical systems or coupled networks with only local connections.
	b. It is a set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head.
	c. It is a physical system in which law of motion implements a rule that defines each output qubit in terms of the input quibits.
	d. It is a minimal physical system.

Question 70

Which class is NOT one of Wolfram's four classes of cellular automata that generate distinctive patterns by evolution from finite initial configurations?

Choose one answer.

	a. The class where pattern disappears with time
	b. The class where pattern evolves to a fixed finite size
	c. The class where pattern behaves chaotically
	d. The class where pattern grows and contracts with time

Question 71

Which class is NOT one of Wolfram's four classes characterized by the effects of small changes in initial configurations?

Choose one answer.

	a. The class with ever-decreasing changes in a region of finite size
	b. The class with no change in final state
	c. The class with changes only in a region of finite size
	d. The class with changes over a region of ever-increasing size

Question 72

Which formal language is NOT one of Wolfram's four types of formal languages distinguished by the computer's memory size?

Choose one answer.

	a. Unrestricted languages with indefinitely large memory
	b. Context-sensitive languages: memory proportional to input word length
	c. Irregular languages: limited memory
	d. Regular languages: no memory

Question 73

Which languages are associated with universal computers?

Choose one answer.

	a. Restricted languages
	b. Unrestricted languages
	c. Irregular languages
	d. Regular languages

Question 74

Which system of equations describes CNN dynamics?

Choose one answer.

	a. Linear equations
	b. Linear differential equations
	c. Nonlinear differential equations
	d. Quadratic differential equations

Question 75

Which type of language does a cellular automaton belong to?

Choose one answer.

	a. Irregular language
	b. Turing language
	c. Informal language
	d. Formal language

Question 76

Which of the following is the law in which systems go towards entropy and complete disorder, destroying any order initially present?

Choose one answer.

	a. Zeroth law of thermodynamics
	b. First law of thermodynamics
	c. Second law of thermodynamics
	d. Third law of thermodynamics

Question 77

Fill in the blank. In a quantum computer _______________ is marked by completion of a cycle of spin manipulation.

Choose one answer.

	a. Output of the computation
	b. Quantum indifferent
	c. Quantum sub-positioned
	d. Spin-1/8 particles

Question 78

Fill in the blank. In classical computations, universes ______________ each other.

Choose one answer.

	a. Do not affect
	b. Affect
	c. Intermingle with
	d. Depend on

Question 79

Fill in the blank. In classical physics, the approximation of universes is _____________.

Choose one answer.

	a. Random
	b. Probabilistic
	c. Self-contained
	d. Pre-determined

Question 80

Fill in the blank. To specify a gate in a quantum computer, it is enough to specify its action on an arbitrary pure state or its action on a(n) _________________ state.

Choose one answer.

	a. Arbitrary computation basis
	b. Differential
	c. Indifferent
	d. Solid

Question 81

How is a program executed on a quantum computer?

Choose one answer.

	a. It is executed by evolution of a finite, nonempty ordered set with elements that are symbols or characters.
	b. It is executed by unitary evolution of an input that is given by the state of the system.
	c. It is executed by binary evolution of an input that is given by the state of the system.
	d. None of the above

Question 82

In Braunstein's book, which type of computer does he refer to when he writes about a machine that is based on a classical computer instructing a machine to manipulate a set of spins?

Choose one answer.

	a. Quantum computer
	b. Sophisticated computer
	c. Advanced computer
	d. All of the above

Question 83

In which problems does a quantum parallelism yield exponential speedup?

Choose one answer.

	a. In problems whose structure uses the red-black trees
	b. In problems whose structure avoids the need to try exponentially many solutions
	c. In problems whose structure avoids the need to try linearly many solutions
	d. None of the above

Question 84

It is important to make sure that which of the following does NOT interrupt the spins in the model of a quantum computer, because the spins could destroy their orientation?

Choose one answer.

	a. Quantum indifference
	b. Unitary evolution
	c. Secondary evolution
	d. Ternary evolution

Question 85

What are non-standard gates that are required to build a quantum computer?

Choose one answer.

	a. PAMOUT and ERASE
	b. FANOUT and MOVE
	c. FANOUT and ERASE
	d. FANIN and ERASE

Question 86

What are the reasonable predictions about when we can reach atomic-scale computations?

Choose one answer.

	a. Within the next two years
	b. Within the next year
	c. Within the next two decades
	d. Within the next decades

Question 87

What does the ERASE gate do?

Choose one answer.

	a. Gives access to protected data
	b. Shifts 8-bit numbers
	c. Stores its input into temporary location
	d. Deletes its input

Question 88

What does the FANOUT gate do?

Choose one answer.

	a. Erases data copies by uncomputing
	b. Backs up data
	c. Multiplies data by uncomputing
	d. None of the above

Question 89

What has to be kept intact, due to entanglement, at intermediate stages in the model of a quantum computer?

Choose one answer.

	a. Spin-1/4 particles
	b. Quantum sub-position
	c. Quantum superposition
	d. Quantum indifference

Question 90

What is a quantum gate?

Choose one answer.

	a. It is a set consisting of a finite-state control, an input tape, a read-only input head, an output tape, and a write-only output head.
	b. It is a physical process whose law of motion implements a rule that defines each output qubit in terms of the input quibits.
	c. A finite, nonempty ordered set with elements that are symbols or characters.
	d. None of the above.

Question 91

What is needed to specify a quantum system?

Choose one answer.

	a. Static constitution
	b. Dynamic constitution
	c. State
	d. All of the above

Question 92

What is one of the biggest problems with the program of miniaturizing conventional computers?

Choose one answer.

	a. Hardware management
	b. Expensive parts
	c. Buggy OS
	d. Dissipated heat

Question 93

What is qubit?

Choose one answer.

	a. A minimal physical system
	b. Part of the memory of a classical computer
	c. A model in which a classical computer emulates a quantum computer
	d. None of the above

Question 94

What is reasonable computation?

Choose one answer.

	a. It is a computation on a minimal physical system.
	b. It is computation through a human brain.
	c. It is computation described by Boolean expressions.
	d. None of the above

Question 95

What is the expectation value?

Choose one answer.

	a. It is the average outcome of minimal physical system.
	b. It is the average outcome of measurement repeated many times.
	c. It is a value of output qubit in terms of the input quibits.
	d. None of the above

Question 96

What is the greatest common divisor (gcd) of 16,321 and 135,749?

Choose one answer.

	a. 1
	b. 163
	c. 37
	d. 57

Question 97

What is the largest problem to build a quantum computer?

Choose one answer.

	a. It is heat.
	b. It is non-sensitive to perturbations.
	c. It is hypersensitive to perturbations.
	d. All of the above

Question 98

What is the requirement for perfect measurement?

Choose one answer.

	a. Measurement in which the observable being measured is sharp.
	b. Measurement in which outcome is the value of the observable.
	c. Measurement which leaves observed value unchanged.
	d. All of the above

Question 99

What kind of particles in the model of a quantum computer is initially in some well-defined state, such as spin-down?

Choose one answer.

	a. Spin-1/16 particles
	b. Spin-1/8 particles
	c. Spin-1/2 particles
	d. Spin-1/4 particles

Question 100

What is the greatest common divisor (gcd) of 756 and 595?

Choose one answer.

	a. 6
	b. 7
	c. 9
	d. 8