Automata, Computability and Complexity:
· They are linked by the question:
O “What are the fundamental capabilities and limitations of computers?”
· The theories of computability and complexity are closely related. In complexity theory, the objective
Is to classify problems as easy ones and hard ones, whereas in computability theory he classification of
Problems is by those that are solvable and those that are not. Computability theory introduces several
Of the concepts used in complexity theory.
· Automata theory deals with the definitions and properties of mathematical models of computation.
· One model, called the finite automaton, is used in text processing, compilers, and hardware design.
Another model, called the context – free grammar, is used in programming languages and artificial
Intelligence.
Strings and Languages:
· The string of the length zero is called the empty string and is written as e.
· A language is a set of strings.
Definitions, Theorems and Proofs:
· Definitions describe the objects and notions that we use.
· A proof is a convincing logical argument that a statement is true.
· A theorem is a mathematical statement proved true.
· Occasionally we prove statements that are interesting only because they assist in the proof of another,
More significant statement. Such statements are called lemmas.
· Occasionally a theorem or its proof may allow us to conclude easily that other, related statements are
True. These statements are called corollaries of the theorem.
(No Ratings Yet)