Introduction to Computing Chapter 2: Language - PDF

# Introduction to Computing ## Chapter 2: Language ### Prof. Achraf El Allali - _Image: A word cloud of common computer related terms, such as computer, data, internet, network, system and information. ## Recap - Computing is the ultimate mental amplifier, mechanizing any intellectual activity....

# Introduction to Computing ## Chapter 2: Language ### Prof. Achraf El Allali - _Image: A word cloud of common computer related terms, such as computer, data, internet, network, system and information. ## Recap - Computing is the ultimate mental amplifier, mechanizing any intellectual activity. - Use of language in computing to describe procedures and execute processes. ## Surface Forms and Meanings - A language is a set of surface forms and meanings, and a mapping between the surface forms and their associated meanings. `<Symbol,Meaning>` - For textual languages, surface forms are linear sequences of characters. - A useful language must be able to express infinitely many different meanings. - _Image: A traffic light with green, yellow and red lights. The text '<Green, Go>', '<Yellow, Caution>' and '<Red, Stop>' are written next to the image._ ## Natural vs Designed Languages - Natural Languages: Complex, evolved over time (e.g., English, Swahili) - Designed Languages: Created for specific purposes, like computer programming languages. ## Language Construction - Language involves three components: Primitives, Means of Combination, and Means of Abstraction. - Primitives: The smallest units of meaning. - Means of Combination: Rules for constructing new elements. ## Example of Word Construction - Example: The word "antifreeze". - "Breakdown: Anti- (against) + freeze (turning into a solid). - New words can be invented using known primitives and rules. ## Means of Abstraction - Abstraction in language allows complex entities to be simplified. - Example: Pronouns like "he," "she," or "it" in natural languages. - In natural languages, there are a limited number of means of abstraction. - The interpretation of what a pronoun abstract in natural languages is often confusing. - Languages for programming computers need means of abstraction that are both powerful and unambiguous. ## Recursive Transition Networks (RTNs) - A method to define languages using nodes and edges. - Simple RTNs can produce different strings by combining paths. - Example: Sentences like "Alice jumps," "Bob runs." - _Image: A diagram of a simple Recursive Transition Network (RTN). The network has four circles, labeled 'Alice', 'Noun', 'Verb', and 'S'. The circles are connected by arrows labeled 'jumps' and 'runs'._ ## Recursive Transition Networks with Cycles - RTNs become more expressive when they include cycles. - Cycles allow the generation of infinitely many sentences. - Example: "Alice runs and Bob jumps and Alice jumps." - _Image: A diagram of an RTN with cycles. The network has four circles, labeled 'Alice', 'Noun', 'Verb', and 'S'. The circles are connected by arrows labeled 'jumps', 'runs', and 'and'._ ## Exercise Draw a recursive transition network that defines the language of the whole numbers: 0, 1, 2, ... ## Solution - _Image: An RTN for whole numbers. The network has two circles, labeled 'WholeNumber' and 'EndWholeNumber'. The circles are connected by arrows labeled '0', '1,9', and '0-9'._ ## Exercise How many different strings can be produced by the RTN below? - _Image: A diagram of an RTN with cycles. The network has four circles, labeled 'Alice', 'Noun', 'Verb', and 'S'. The circles are connected by arrows labeled 'jumps', 'runs', 'eats', 'quickly', and 'slowly'._ ## Solution There are 10 total strings, corresponding to each path through the RTN to the final S state: Alice jumps, Alice eats slowly, Alice eats quickly, Alice runs slowly, Alice runs quickly, Bob jumps, Bob eats slowly, Bob eats quickly, Bob runs slowly Bob runs quickly - _Image: A diagram of an RTN with cycles. The network has four circles, labeled 'Alice', 'Noun', 'Verb', and 'S'. The circles are connected by arrows labeled 'jumps', 'runs', 'eats', 'quickly', and 'slowly'._ ## Subnetworks - More expressive RTNs can label edges with subnetworks instead of just direct outputs. - A subnetwork is identified by the name of its starting node. - When an edge labeled with a subnetwork is followed, the traversal jumps to that subnetwork. - The traversal follows a path within the subnetwork until a final node is reached. - After reaching a final node, the traversal returns to complete the original edge. - _Image: Two diagrams: Figure 2.3: A Recursive Transition Network with subnetworks, Figure 2.4: Alternate Noun subnetwork._ ## Keeping track of paths through RTNs - A single marker is enough to track paths through RTNs without subnetworks by moving it from the start to the final node. - Tracking paths in RTNs with subnetworks is more complex, as we need to remember where we are in both the current network and where to continue after completing a subnetwork. - Subnetworks can be nested within other subnetworks, so a method is needed to track multiple jump points. - A stack is a useful tool for tracking subnetworks, similar to how trays are stacked in a cafeteria, where only the top tray is accessible. - We use a stack of nodes, where the top of the stack represents the next node to process, and new nodes are pushed as subnetworks are entered. - _Image: Two diagrams: Figure 2.3: Recursive transition network with subnetworks. Figure 2.5: RTN generating "Alice runs"._ ## Replacement Grammars - Another way to define languages. - Backus-Naur Form (BNF) is used to describe languages through a set of replacement rules. - Rules in a Backus-Naur Form grammar have the form: `nonterminal ::→ replacement` - Recursive rules make BNF powerful, allowing infinite language generation. ## BNF of our earlier RTN 1. Sentence::→ Noun Verb 2. Noun:: Alice 3. Noun:: Bob 4. Verb: jumps 5. Verb :: runs - _Image: A diagram of the previous RTN, with a text box underneath containing the BNF derivation of "Alice runs"._ ## Recursive Grammar - A grammar is recursive if the grammar contains a nonterminal that can produce a production that contains itself. - `Sentence :: Sentence and Sentence` - Now, how many sentences can we generate? Infinitely many ## Example: Whole Numbers Grammar - BNF can define numbers: - Example rule: Number :: Digit MoreDigits - More Digits :: - MoreDigits :: Number - Digit :: 0 - Recursive rules enable generation of all whole numbers. ## Circular vs. Recursive Definitions. - The rule "MoreDigits:: ε" allows for the replacement of MoreDigits with nothing, enabling string termination and preventing infinite recursion. - Without this rule, the grammar would be stuck in a circular definition, continuously producing MoreDigits without ever reaching a terminal string. - The "MoreDigits :: ε" rule acts as a base case, turning the recursive definition into a meaningful one by allowing the generation of finite strings. ## Condensed Notation - Whole numbers BNF - Number :: Digit MoreDigits - MoreDigits :: → & (empty string) | Number - Digit :: - 0|1|2|3|4|5|6|7|8|9 ## Terminals and non-terminals - Terminals: - Basic symbols from which strings in the language are formed. - 'leaf" symbols in the grammar, meaning they cannot be broken down ➤ Examples include actual words or characters, like "cat" or "dog". - Non-terminals: - Abstract symbols that can be replaced by other symbols (terminals or non-terminals) - According to the production rules. They represent structures in the language that can be expanded. - For example, <noun-phrase> is a non-terminal that could be expanded into terminals like "the cat" or "a dog". ## Advantages of BNF and RTNs - BNF Advantages: - More compact and formal for defining grammar rules. - Easy to use in automated grammar checkers and parsers. - Widely used in programming language specifications. - RTN Advantages: - Easier to visualize and understand complex, recursive structures. - Helpful for teaching and understanding the flow of parsing in a language. - Can be extended to handle more complex constructs like lookahead in parsing. ## Exercise The grammar for whole numbers we defined allows strings with non-standard leading zeros such as "000" and "00005". Devise a grammar that produces all whole numbers (including "0"), but no strings with unnecessary leading zeros. ## Solution To eliminate the leading zeros, we need to add a new nonterminal for NonZeroDigit, and a special rule for 0. - Number :: 0 - Number :: - NonZeroDigit MoreDigits - More Digits :: → - More Digits :: Digit MoreDigits - Digit :: 0 - Digit :: NonZeroDigit - NonZeroDigit :: 1219 ## References - https://computingbook.org/Language.pdf ## Contact - **Email:** [email protected] - **Websites:** bioinformatics.um6p.ma - **Office:** Teaching Building, 3rd floor - _Image: A collage of many different images. The text, "Introduction to Computing - Explorations in Language, Logic, and Machines", is written next to the image._