Lecture Discrete mathematics and its applications (7/e) – Chapter 13: Modeling computation. This chapter presents the following content: Languages and grammars, finite-state machines with output, finite-state machines with no output, language recognition, turing machines. | Modeling Computation Chapter 13 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Languages and Grammars Finite-State Machines with Output Finite-State Machines with No Output Language Recognition Turing Machines Languages and Grammars Section Section Summary Phrase-Structure Grammars Types of Phrase-Structure Grammars Derivation Trees Backus-Naur Form Introduction Syntax (form of a sentence) vs. semantics (meaning of a sentence) The sentence the frog writes neatly is a valid sentence according to the rules of English grammar. That is, it is syntactically correct, even though it’s nonsensical (unless we are talking about a fantasy world). The sequence of words swims quickly mathematics is not a valid sentence according to the rules of English grammar. Grammars The rules that specify the syntactically correct sentences of a natural language such as English are complex. Instead of studying natural languages, we can define formal languages that have well-defined rules of syntax. These rules of syntax are important both in linguistics (the study of natural languages) and in the study of programming languages. An Example Grammar An example sequence of replacements: noun phrase verb phrase article adjective noun verb phrase article adjective noun verb adverb the adjective noun verb adverb the large noun verb adverb the large rabbit verb adverb the large rabbit hops adverb the large rabbit hops quickly a sentence is made up of a noun phrase followed by a verb phrase; a noun phrase is made up of an article followed by an adjective followed by a noun, or a noun phrase is made up of an article followed by a noun; a verb phrase is made up of a verb followed by an adverb, or a verb phrase is made up of a verb; an article is a, or an article is the; an adjective is large, or an adjective is hungry; a noun is rabbit, or a noun is mathematician; a verb is eats, . | Modeling Computation Chapter 13 Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Languages and Grammars Finite-State Machines with Output Finite-State Machines with No Output Language Recognition Turing Machines Languages and Grammars Section Section Summary Phrase-Structure Grammars Types of Phrase-Structure Grammars Derivation Trees Backus-Naur Form Introduction Syntax (form of a sentence) vs. semantics (meaning of a sentence) The sentence the frog writes neatly is a valid sentence according to the rules of English grammar. That is, it is syntactically correct, even though it’s nonsensical (unless we are talking about a fantasy world). The sequence of words swims quickly mathematics is not a valid sentence according to the rules of English grammar. Grammars The rules that specify the syntactically correct sentences of a natural language such as English are complex.
