:math:`\rightarrow` hit | ran | ate :math:`\rightarrow`

| :math:`\rightarrow` Fritz | ball

:math:`\rightarrow` the | an | a Any grammar has variables (also called "non-terminals") and terminals. Terminals are generally strings. Variables are things that ultimately are replaced by terminals. In this example, we put :math:`<>` brackets around all of the variables to make them easier to recognize. We won't always do this. The grammar has a collection of productions. In this example, each production replaces a variable with some series of variables and terminals. Ultimately, all "sentences" in the "language" are generated by starting with the variable, and using productions to reach the desired sentence. Examples ~~~~~~~~ Deriving a sentence: To derive a sentence, start at the starting point of the grammar and do replacements until you can do no more replacements. A variable in the grammar can be replaced by the right hand side of its rule:: Fritz hit the ball -> -> -> Fritz -> Fritz hit -> Fritz hit

-> Fritz hit the -> Fritz hit the ball Can we derive these sentences? If not, can we change the grammar?:: The ball hit Fritz The ball ate the ball * A sentence is syntactically correct if it follows the rules (the grammar can dervive it) * A sentence is semantically correct if it has "meaning" Formal definition of a grammar ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A grammar :math:`G = (V, T, S, P)` where * :math:`V` is a finite set of variables (nonterminals). * :math:`T` is a finite set of terminals (generally, these are strings). * :math:`S` is the start variable (:math:`S \in V`). * :math:`P` is a set of productions (rules). :math:`x \rightarrow y` means to replace :math:`x` by :math:`y`. Here, :math:`x \in (V \cup T)^+, y \in (V \cup T)^*`. Question: What are :math:`S, T, V, P` in the "english" grammar example above? Notation ~~~~~~~~ .. math:: \begin{array}{ll} w \Rightarrow z & w\ \mbox{derives}\ z\\ w \stackrel{*}{\Rightarrow} z & \mbox{derives in 0 or more steps}\\ w \stackrel{+}{\Rightarrow} z & \mbox{derives in 1 or more steps}\\ \end{array} Given grammar :math:`G = (V, T, S, P)`, define .. math:: L(G)= \{w \in T{}^{*} \mid S \stackrel{*}{\Rightarrow} w\} Now, try to describe in words: What is the language of the grammar? Answer: It is all strings formed over the alphabet (or set of terminals, note that :math:`T^*` is all possible strings over T), SUCH THAT if you start with S (the start symbol in the grammar), you can derive the string. **Example** :math:`G=(\{S\}, \{a,b\}, S, P)` :math:`P=\{S \rightarrow aaS, S \rightarrow b\}` :math:`L(G) =` ? Answer: :math:`\{b, aab, aaaab, ... \} = \{(aa)^nb | n \ge 0\}` **Example** :math:`L(G) = \{a^nccb^n | n > 0\}` :math:`G =` ? Answer: :math:`S \rightarrow aSb | aAb` :math:`A \rightarrow cc` **Example** :math:`G = (\{S\}, \{a,b\}, S, P)` :math:`P = \{S \rightarrow aSb, S \rightarrow SS, S \rightarrow ab\}` Which of these strings :math:`aabb, abab, abba, babab` can be generated by this grammar? Show the derivations. :math:`L(G) =` ? Answer: The language of matching parenthesis where :math:`a` is left paren, and :math:`b` is right paren. :math:`S \rightarrow aSb \rightarrow aabb` :math:`S \rightarrow SS \rightarrow abS \rightarrow abab` Cannot derive :math:`abba, babab`. WHY? Nothing ends with :math:`a`, nothing starts with :math:`b`. .. avembed:: Exercises/FLA/CharacterizeLang1.html ka :module: FLConcepts :points: 1.0 :required: True :threshold: 5.0 :id: 184176 :exer_opts: JXOP-debug=true&JOP-lang=en&JXOP-code=java :long_name: Characterizing a Language, Problem 1 .. avembed:: Exercises/FLA/CharacterizeLang2.html ka :module: FLConcepts :points: 1.0 :required: True :threshold: 5.0 :id: 184177 :exer_opts: JXOP-debug=true&JOP-lang=en&JXOP-code=java :long_name: Characterizing a Language, Problem 2 Automata -------- .. inlineav:: AutomataCON dgm :align: center Abstract model of a digital computer. Note that in the control unit, the numbers represent "states", which are the specific positions on the dial that the arrow may point to. While this picture shows the physical components of the "computer", it is not showing the control behavior (what to do when we are in a given state with a given symbol on the current square of the tape, and a given value is at the current position in the storage unit). This control behavior is like the "software" of the computer. There is a program associated with the control unit, and the input is processed once from left to right. Some versions have an additional storage unit. We will define specific automata throughout the semester. This is the topic for the chapter on :ref:`DFAs `. .. odsascript:: DataStructures/FLA/FA.js .. odsascript:: AV/VisFormalLang/Intro/AutomataCON.js