Formal Grammars ©  Fabian M. Suchanek 55
Overview 2 Formal Languages Regular languages Context‐free languages Context‐sensitive languages Recursively enumerable languages >alphabet
Def: Alphabet, Word An  alphabet  is a set of symbols. We will use as alphabet always implicitly the set of all unicode characters. 3 A={a,b,c,d,e,f,0,1,2,3,4,5,6,7,8,9} A={0,...9,a...,z,A...Z,!,?,...} word  over an alphabet A is a sequence of symbols from A. Since we use the alphabet of unicode characters, words are just strings. hello!, 42, 3.141592, Douglas and Sally  also with spaces!
Def: Language language  over an alphabet S is a set of words over S. 4 Examples of interesting languages: The language of French words: {aimer, chat, sur, ...} The language of French sentences: {J’aime les chats, Le chat chante,...} The language of valid Java programs: {public static void main(...)..., ...} The language of terminating Java programs: {public...,...} The language of algebraic expressions: {(1+2)*3, (7-2)+(7+2), ...} The language of prime numbers: {2, 3, 5, 7, 11, ...} The language of person names: {Thomas Paine, Bertrand Russel,...} We want to do two things with languages: 1) decide whether a given word belongs to the language 2) generate the words of the language
decision problem  is the question of whether a given string ( e.g. a natural number ) belongs to a language  ( e.g. the language of prime numbers ). 5 Def: Decision problem 4 15 18 112 42 2 7 19
It turns out that the decision problem is more difficult for certain types of languages than for others. Languages are grouped as follows: 6 The Chomsky Hierarchy Regular languages Context‐free languages Context‐sensitive languages Decidable languages All languages any language that can be recognized by a terminating algorithm e.g., most natural languages e.g., algebraic expressions recognizeable by regular expressions Semi‐Decidable languages e.g., the language of programs that terminate
There are several formalisms that to recognize/generate the words of a language: •  grammars (e.g., context-free grammars) •  simple automata (e.g., finite state automata) •  other formalisms (Turing machines, regular expressions) The main properties are: •  each level in the Chomsky hierarchy has its own type of grammar     (the decidable and semi-decidable ones have the same type) •  for each type of grammar, there is usually an equivalent    automaton and equivalent other formalisms •  most formalisms can not just recognize the languages,     but also generate them 7 Recognizing Languages
(formal) grammar  is a tuple of •  A finite set   of nonterminal symbols (we write them in upper case) •  A start symbol    •  A finite set   of terminal symbols that is disjoint from   (lower case) •  A finite set   of production rules, each rule of the form         8 Formal Grammars where   is the Kleene star, which allows repetition of the elements. Example: N={S,NP,VP} s=S ={they, run, love, you} P ={ S NP VP, NP they, NP you, VP love, VP run }
string of a grammar  (N, s,  , P) is an element of   (we use Greek letters for strings). The grammar  derives  a string  from a string    in one step, if there is a  production rule  . It  derives a word  (of terminal symbols) if there is a sequence of one step derivations from the start symbol to the word. The  language of a grammar  is the set of all derivable words. 9 Language of a Grammar Example: N={S,NP,VP} s=S ={they, run, love, you} P ={ S NP VP, NP they, NP you, VP love, VP run }  NP VP   you VP   you run The grammar can both generate the words of the language (by derivation) and recognize them (by parsing, i.e., by finding the derivations for the word).
Overview 10 Formal Languages Regular languages Context‐free languages Context‐sensitive languages Recursively enumerable languages
(right) regular grammar  has only productions of the following form: •   , where   is a non-terminal and   is a terminal •   , where   and   are non-terminals and a is a terminal •   , where   is a non-terminal and   is the empty string 11 Regular Grammar Example: N={S,A,B} s=S ={a,b} P ={ S aA, S bB, A aA, B bB, A  }  A   aA   aaA   aa
The languages that can be generated/recognized by a regular grammar are the  regular languages  of the Chomsky Hierarchy. 12 Regular Languages Examples for regular languages: •  search/replace patterns in editors •  simple named entities •  numbers, dates, quantities Regular languages are closed under •  union •  intersection •  complement •  concatenation •  iteration (Kleene star)
Def: Finite State Machine finite state machine  (FSM) is a directed multi-graph, where each edge is labeled with a symbol or the empty symbol  . One node is labeled “start” (typically by an incoming arrow). Zero or more nodes are labeled “final” (typically by a double circle). 13 a b Start Final d c See a more formal definition in  Wikipedia The empty transition can be walked without accepting a symbol: Multiple edges are written as: a, b a b :=
Recognizing words An FSM  recognizes  (also: generates, accepts) a string, if there is a path from the start node to a final node whose edge labels are the string. 14 ad bccd bb >tasks a b Start Final d c
Task: FSM Find strings generated by the following FSM (Betelgeuse 7 language): 15 Final l Start c x Final j >tasks
Task: FSM Draw an FSM that accepts the following strings Draw an FSM that accepts the following strings 16 br kbr brbr kbrbr brbrbr kbrbrbr ... ling lingping long pong lingpong ping pingpong
FSMs and Regular Grammars Every Right Regular Grammar can be transformed into an equivalent FSM as follows: •  introduce a state for every non‐terminal •  let the grammar start symbol be the initial state of the automaton •  introduce a final state  •  for every rule  , add a transition from   to   with symbol  •  for every rule  , add a transition from   to   with symbol  17 Example: N={S,A,B}, s=S,  ={a,b} P ={ S aA, S bB, A aA, B bB, A  } S A B a b F a b Vice versa, every FSM can be transformed to a grammar. [e.g.,  Zhang&Qian, 2013 ]
Def: Regular expression regular expression  (regex) over an alphabet   is one of the following: • the empty string • an element of  • a string of the form XY    • a string of the form (X|Y)  • a string of the form (X)* where X and Y are regexes A regex is associated to a language: 18 its language the regular expression (0 is a special regex that cannot appear as part of other regexes. It represents the empty language and does not match any string.) *   for symbols  >details
Regular expression cheat sheet L(a) = {a} L(ab) = {ab} L(a | b) = {a, b} L(a*) = { , a, aa, aaa, ...} L(a+) := L(aa*) L([a-z]) := L(a|b|...|z) L(a{2,4}) := L(aa|aaa|aaaa) L(a{3}) := L(aaa) L(a?) := L(  | a) L(.) := {a|b|..|A|...|0|...|!|$|...} L(\.) := {.} 19 Simple symbol Concatenation Disjunction Kleene star shorthand for “one or more” shorthand for a range shorthand for a given number shorthand for a given number shorthand for “optional” shorthand for “any symbol” escape sequence for special symbols
How can we match regexes? Douglas Adams fictional character names: [A-Z][a-z]*ch[a-z]* The Hitchhiker meets the Golgafrinchan civilisation, but falls in love with a girl named Fenchurch. 20 ?
Transforming a regex to a FSM (1) 1. Simplify the regex to contain only    concatenation, alternation, kleene star 21 2. Start with this configuration: REGEX 3. Handle alternation: X|Y X Y Every regex can be transformed into an equivalent FSM (and vice versa):
Transforming a regex to a FSM (2) 22 4. Handle concatenation: XY X Y 5. Handle Kleene star: (X)* X 6. Proceed recursively, until all edges are single symbols
Runtime of FSMs Given a word of length    and given an FSM with   states, determining whether the FSM accepts the word • takes   time if no state has several outgoing edges   with the same label •   else (by determinizing on the fly) 23 There is a looooot more to say about FSMs, e.g.: • making them deterministic • compressing them • making them more powerful • learning FSMs from examples >programming
Regexes in programming Regex   Simplified regex   FSM   Matcher His favorite numbers are 42, 4200, and 19. your programming language 24 42(0)+ 420(0)* 4 2 0 0 you >programming
Example: Regexes in Java Pattern pattern = Pattern.compile("42(0)+"); Matcher matcher = pattern.matcher("His favorite numbers are..."); while(matcher.find())    System.out.println(matcher.group()); 25 4200 His favorite numbers are 42, 4200, and 19. >programming
Example: Regexes in Python import re pattern = re.compile("42(0)+") match = re.search(pattern, line) if match!=None:      print(match.group()) 26 4200 His favorite numbers are 42, 4200, and 19.
Regular languages 27 The following statements are equivalent for a language  : •    is a regular language •    can be recognized by a regex •    can be recognized by a finite state automaton •    can be generated by a finite state automaton •    can be recognized by a regular grammar •    can be generated by a regular grammar Recognizing a word of a regular language takes a time that is quadratic in the number of states of the FSM.
Not all languages are regular Take the language of algebraic expressions:     L={ (1+2)*3, 4*(5+(6/7)), ...} Assume there was an automaton   with   states that recognizes this language. Consider the following word  :     (((...( 42 )...))) When   recognizes  , it has to pass through at least one state   twice during the opening parantheses. Be   the number of parantheses recognized between two subsequent passes through  . Then  recognizes the following word   as well:      (((... (...(  42 )...))) 28  opening parantheses and   closing ones  opening parantheses and   closing ones  opening parantheses This proof is known as the  pumping lemma .
Overview 29 Formal Languages Regular languages Context‐free languages Context‐sensitive languages Recursively enumerable languages
Context‐free grammar 30 context‐free grammar  has only productions where the left‐hand‐side is a single non‐terminal. Example: N={S,NP,VP} s=S ={they, run, love, you} P ={ S NP VP, NP they, NP you, VP love, VP run }
Context‐free languages 31 The languages that can be generated/recognized by a context‐free grammar are the  context‐free languages  of the Chomsky Hierarchy. Examples for context‐free languages: •  algebraic expressions •  simple programming languages •  simplistic models of natural language sentences ...or anything with nested structures Context‐free languages are closed under •  union •  concatenation •  Kleene star ...but not under intersection or complement. >phrase structure
Phrase Structure Grammars Alizée is the mother of the little Annily. 32 PN PN V DET N PREP DET ADJ NP NP NP NP PP VP  S S -> NP VP NP -> PN VP -> V NP -> DET ADJ N PN -> Alizée DET -> the ... try it out >phrase structure (Some approaches build only binary trees)
Alizée, who has a beautiful voice, is the mother of Annily. 33 PN PN V DET N PREP NP NP NP NP PP VP  S PN DET ADJ NP SUB VP  V COMP The grammar identifies a sub‐ordinate phrase. Phrase Structure Grammars
34 Pushdown Automaton Given an input alphabet  , a stack alphabet  , and a start symbol  , pushdown automaton  (PDA) is a directed multi‐graph, were each edge is labeled with •  a symbol   to read from the input (or  ) •  a symbol   to pop from the stack (or  ) •  a sequence of symbols   to push onto the stack One node is labeled “start”, and zero or more nodes are labeled “final”. read:  pop:  push:  read: ( pop:  push: 1 read: ) pop: 1 push: 
35 Running a PDA configuration  of a PDA is a triple of a node  , an input string  , and a stack  . The  step relation  is defined for all   as the following relation between configurations:        if there is an edge from   to   that is labeled with “read  , pop  , push  ”. A word   is recognized by the PDA, if  where   is the start node and   is a final node. The  language  of a PDA is the set of recognized words. read:  pop:  push:  read: ( pop:  push: 1 read: ) pop: 1 push: 
36 Context‐free grammars & PDAs For every context‐free grammar there is an equivalent pushdown automaton and vice versa. To construct the PDA for a context‐free grammar, normalize the rules so that they are all of the following forms:      Be    the start symbol. Then construct the (non‐deterministic) PDA as: read:  pop:  push:  ... for every rule read:  pop:  push:  ... for every rule read:  pop:  push:  read:  pop:  push: 
37 Limitations of context‐free grammars Context‐free grammars need extensive duplication of non-terminal symbols to model dependencies between words: Various remedies have been devised, e.g., using arguments that can be compiled away: ...or devising “weakly context-sensitive grammars”. No context‐free grammar can recognize Sentence -> FirstPersonSingularSentence | SecondPerson... FirstPersonSingularSentence-> “I” FirstPersonSingularVerbPhrase FirstPersonSingularVerbPhrase -> “go” | “love” | ... Sentence( ) -> NounPhrase( ) VerbPhrase( ) NounPhrase(1,s) -> “I” L={a b c  :   }
Context‐free Languages 38 The following statements are equivalent for a language   : •    is context‐free •    can be recognized by a pushdown automaton •    can be generated by a pushdown automaton •    can be recognized by a context‐free grammar •    can be generated by a context‐free grammar Recognizing a word of a regular language takes polynomial time. Every regular language is a context‐free language.
Overview 39 Formal Languages Regular languages Context‐free languages Context‐sensitive languages Recursively enumerable languages
Context‐sensitive grammar 40 context‐sensitive grammar  has only productions of the form      ...where   is a non‐terminal,   is a non-empty string, and   and  are strings (consisting of terminal and/or non-terminals). The languages that can be generated/recognized by a context‐sensitive grammar are the  context‐sensitive languages  of the Chomsky Hierarchy. Example: N={S,NP,VP, 1s, 2s, 3s, 1p, 2p, 3p} s=S ={they, run, love, you} P ={ S NP 3p VP 3p, NP 3p they 3p, VP 3p run 3p, 3p ,...} >non‐contracting
Non‐Contracting grammar 41 An  essentially non‐contracting grammar  is a grammar where the left‐hand‐side of a production is never longer than its right‐hand‐side, except if the right‐hand‐side is the empty word. Every essentially non‐contracting grammar can be transformed into a context‐sensitive grammar and vice versa.
Turing Machine 42 Given a tape alphabet  , a blank symbol  , and an input alphabet , a  turing machine  is a labeled directed multi‐graph, where each edge is labeled with •  a symbol   to read •  a symbol   to write •  a direction (left or right) to move the read‐write head One node is labeled “start”, and zero or more nodes are labeled “final”. read: e write: e move: R read: h write: f move: R read: m write: m move: R read: o write: e move: R An FSM is a Turing machine that can just read and move right. A Pushdown Automaton is a Turing machine that can just read and move right, and that stores a stack on the tape.
Running a Turing Machine 43 An  configuration  of a Turing machine is a tuple of •  a current node  •  a left string  •  a right string  The  step relation  is defined between two configurations for all   as         if there is an edge from   to   labeled with “read  , write  , move R”, and as   if the move is L. A word   is recognized if   such that   is a final state, where   is an infinite sequence of blanks. read: e write: e move: R read: h write: f move: R read: m write: m move: R read: o write: e move: R
Context‐sensitive grammars 44 The following are equivalent •  a language   is context‐sensitive •    can be recognized by a Turing machine with a bounded band     (whose length does not depend on the input) •    can be recognized by a context‐sensitive grammar All regular and context‐free languages are context‐sensitive, but not all languages are context‐sensitive. Consider, e.g., the language of pairs of equivalent regular expressions with exponentiation. read: e write: e move: R read: h write: f move: R read: m write: m move: R read: o write: e move: R
Overview 45 Formal Languages Regular languages Context‐free languages Context‐sensitive languages Recursively enumerable languages
Unrestricted Grammars 46 An  unrestricted grammar  is  a grammar with arbitrary productions. For every unrestricted grammar, there exists a Turing Machine that recognizes the words of the language, and vice versa. read: e write: e move: R read: h write: f move: R read: m write: m move: R read: o write: e move: R S -> hoMe M -> mM M -> 
Decidable language 47 decidable language  is a language for which there exists a total Turing Machine  (= one that halts on all inputs) that recognizes it. read: e write: e move: R read: h write: f move: R read: m write: m move: R read: o write: e move: R All regular, context‐free, and context‐sensitive languages are decidable.
Semi‐decidable language 48 semi‐decidable  (recursively enumerable) language is a language  for which there exists a Turing Machine   so that •  if  , then   halts and accepts  •  if  , then   either does not halt, or does not accept  Examples of semi‐decidable, but not decidable problems: •  Halting problem: Does the program terminate? •  Language equality: Do two context-free grammars    generate the same language? •  Hilbert’s 10th problem: Does            have a solution? >Halting&FOL
Halting Problem 49 The  halting problem  is the decision problem of all Turing Machines (equivalently: all computer programs) that terminate (= do not loop foerver). This problem is not decidable. Proof: Assume that there were a Turing Machine   so that  iff program   terminates. Then construct the program   with          if   then loop Then ask  . If  , then   does not terminate. The problem is not decidable, but semi‐decidable. Proof: Construct a Turing Machine that runs the program and accepts it when it terminates. >FOL
The  Entscheidungsproblem  is the decision problem of all first‐order‐logic (FOL) formulae that are valid. This problem is semi‐decidable. Proof: We can systematically enumerate all valid formulae and check if the input is one of them: 50 Def: Entscheidungsproblem >proof ... The problem is not  decidable. Proof idea: We can construct a Turing Machine that halts iff the formula is valid.
Every Turing Machine M can be transformed to a FOL formula , such that if read 'h', write 'f', move right if read 'o', write 'e', move right if read 'm' or 'e', move right 51 Turing Machine in FOL h o m m e M: .
Proof: Assume that the Entscheidungsproblem were decidable, i.e. assume that there is an algorithm A such that    iff   is valid Then A can be used to decide whether  is valid for a Turing Machine M. => A decides the halting problem (impossible) 52 Why FOL is not decidable
The Entscheidungsproblem is decidable if we consider only certain subsets of FOL. Examples: •  Propositional logic (i.e., no quantifiers) •  Horn rules •  Bernays‐Schönfinkel formulae,    i.e., formulae of the form             without function symbols  •  Description logic 53 Decidable subsets of FOL ->description-logics
Any decision problem that is effectively computable (= can be decided by a human with paper and pencil) can be computed by •  a Turing Machine,  or, equivalently, by  •    calculus •  general recursive functions. 54 Church‐Turing Hypothesis