Topic 7

Lesson 7. Abstract Alphabet and Formal Grammars

Objective: involves a hierarchical acquisition of knowledge from a basic understanding of the structure of a language to the ability to construct formal grammars. At the lowest level, Knowing/Remembering, the student must define the concept of an abstract alphabet, list the main components of a formal grammar (the set of terminal symbols V_T, the non-terminal symbols V_N, the initial symbol S, and the set of inference rules P), and name the two main types of rules that govern a language: syntax and semantics. The next level, Understanding, requires the student to explain the difference between natural and formal languages ​​(e.g., programming languages), interpret the concept of an alphabetic operator as a mapping that transforms one string of symbols into another, and formulate the difference between terminal and non-terminal symbols. The Applying level requires the student to demonstrate practical use of knowledge, in particular, to apply the inference rules of a simple generative grammar to generate several language chains (e.g., L(G) = {aⁿbⁿ | n > 0}), and to solve a problem of determining the class of a formal language (e.g., context-free) based on its inference rules. The fourth level, Analyzing, requires the student to compare the classification of formal grammars, distinguish between the concepts of syntax (rules for constructing sentences) and semantics (rules for giving meaning), and analyze the impact of recursion on the possibility of constructing an infinite set of words in a language. At the fifth level, Evaluating, the student must justify the importance of formal grammars for creating computer programming languages, criticize the shortcomings of natural languages ​​(such as the presence of exceptions) for use in algorithmic systems, and also evaluate the importance of a computational system consisting of an abstract alphabet and a set of permissible operations for formalizing algorithmic processes. At the highest level, Creating, the student must develop (plan) his own formal grammar to describe the syntax of a new word class, and also design (create) a set of inference rules that allow generating a certain formal language.