Chapter ObjeCtives
After studying this chapter, you will be able to:
• See how algebraic structures, finite-state machines, and Turing machines are
all models of various kinds of computation, and how formal languages attempt
to model natural languages.
• Recognize certain well-known group structures.
• Prove some properties about groups.
• Understand what it means for groups to be isomorphic.
• Be able to construct group codes for single-error correction of binary m-tuples.
• Be able to decode received n-tuples for a single-error correcting perfect code.
• Trace the operation of a given finite-state machine on an input string.
• Construct finite-state machines to recognize certain sets.
• For a given finite-state machine, find an equivalent machine with fewer states
if one exists.
• Build a circuit for a finite-state machine.
• Trace the operation of a given Turing machine on an input tape.
• Construct Turing machines to perform certain recognition or computation tasks.
• Understand the Church–Turing thesis and what it implies for the Turing machine as a model of computation.
• Be aware of the P = NP question regarding computational complexity.
• Given a grammar G, construct the derivation of strings in L(G).
• Understand the relationship between different classes of formal languages and
different computational devices.
Your team at Babel, Inc., is writing a compiler for a new programming language, currently code-named ScrubOak after a tree outside your office window. During the first
phase of compilation (called the lexical analysis phase) the compiler must break down
statements into individual units called tokens. In particular, the compiler must be able
to recognize identifiers in the language, which are strings of letters, and also recognize the two keywords in the language, which are if and in.
Question: How can the compiler recognize the individual tokens in a statement?
9 9
Modeling Arithmetic, Computation,
and Languages
C h a p t e r
685
After studying this chapter, you will be able to:
• See how algebraic structures, finite-state machines, and Turing machines are
all models of various kinds of computation, and how formal languages attempt
to model natural languages.
• Recognize certain well-known group structures.
• Prove some properties about groups.
• Understand what it means for groups to be isomorphic.
• Be able to construct group codes for single-error correction of binary m-tuples.
• Be able to decode received n-tuples for a single-error correcting perfect code.
• Trace the operation of a given finite-state machine on an input string.
• Construct finite-state machines to recognize certain sets.
• For a given finite-state machine, find an equivalent machine with fewer states
if one exists.
• Build a circuit for a finite-state machine.
• Trace the operation of a given Turing machine on an input tape.
• Construct Turing machines to perform certain recognition or computation tasks.
• Understand the Church–Turing thesis and what it implies for the Turing machine as a model of computation.
• Be aware of the P = NP question regarding computational complexity.
• Given a grammar G, construct the derivation of strings in L(G).
• Understand the relationship between different classes of formal languages and
different computational devices.
Your team at Babel, Inc., is writing a compiler for a new programming language, currently code-named ScrubOak after a tree outside your office window. During the first
phase of compilation (called the lexical analysis phase) the compiler must break down
statements into individual units called tokens. In particular, the compiler must be able
to recognize identifiers in the language, which are strings of letters, and also recognize the two keywords in the language, which are if and in.
Question: How can the compiler recognize the individual tokens in a statement?
9 9
Modeling Arithmetic, Computation,
and Languages
C h a p t e r
685