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

	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.

.

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

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

.

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

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

.

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.

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

.

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.

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

.

Finite-state automata accept only what type of languages?

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

.

Grammars do which of the following?

	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

.

How can sentential forms in type 0 grammar be displayed?

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

.

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

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

.

How many types of grammars are there?

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

.

What are pushdown transducers whose output components are ignored called?

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

.

What is a deterministic machine?

	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.

.

What is a halting computation?

	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

.

What is a pushdown transducer?

	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

.

What is a string?

	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

.

What is representation of information?

	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.

.

What is the definition of a finite-state automaton?

	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

.

What is the most frequently used criteria to compare strings?

	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.

.

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

	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

.

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

	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

.

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

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

.

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

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

.

Which type of program accepts context-free language?

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

.

What is the best description of an alphabet?

	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

.

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

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

.

What are the four DNA nucleotides?

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

.

What are the good points of DNA computing?

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

.

What do biochemical computers depend on to achieve computational functionality?

	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.

.

What do biocomputers depend on when they perform computations?

	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.

.

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

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

.

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

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

.

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

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

.

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

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

.

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

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

.

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

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

.

What operations are usually performed on DNA sequences?

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

.

What to bioelectrical computers depend on to perform computation?

	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.

.

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

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

.

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

	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

.

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

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

.

Why is it economically beneficial to use biocomputers?

	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

.

What is DNA?

	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

.

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

	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

.

How are genetic algorithms different from classical optimization algorithms?

	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

.

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

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

.

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

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

.

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?

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

.

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

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

.

What is the difference between patterns and classes?

	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

.

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

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

.

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

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

.

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

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

.

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

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

.

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

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

.

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

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

.

Which observation is the basis of genetic algorithms?

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

.

Which of the following best describes a classification problem?

	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

.

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

	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

.

Who is John Holland?

	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

.

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

	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.

.

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

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

.

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

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

.

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?

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

.

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?

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

.

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

	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

.

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

	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

.

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?

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

.

What is a Cellular Wave Computer?

	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 flows and solutions of differential equations.
	c. A finite, nonempty ordered set with elements that are symbols or characters.
	d. None of the above

.

What is Cellular Neural Network?

	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.

.

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

	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

.

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

	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

.

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

	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

.

Which languages are associated with universal computers?

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

.

Which system of equations describes CNN dynamics?

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

.

Which type of language does a cellular automaton belong to?

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

.

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

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

.

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

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

.

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

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

.

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

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

.

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.

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

.

How is a program executed on a quantum computer?

	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

.

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?

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

.

In which problems does a quantum parallelism yield exponential speedup?

	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

.

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?

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

.

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

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

.

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

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

.

What does the ERASE gate do?

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

.

What does the FANOUT gate do?

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

.

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

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

.

What is a quantum gate?

	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.

.

What is needed to specify a quantum system?

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

.

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

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

.

What is qubit?

	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

.

What is reasonable computation?

	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

.

What is the expectation value?

	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

.

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

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

.

What is the largest problem to build a quantum computer?

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

.

What is the requirement for perfect measurement?

	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

.

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

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

.

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

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

.