1.1.1 Phrase-structure Grammars

  1. What is a "vocabulary " denoted as V?
    String over V?
    • It is a finite non empty set of symbols.
    • String over V is a finite length string made up of symbols that are in the vocabulary V.
  2. What is lambda in the vocabulary?
    • Lambda is a empty string also called null string.
    • It only contains no symbols at all but is still a string.
    • Kind of lik x as an unassigned variable containing nothing.
  3. What does a full phrase structure grammar consist of? How is it denoted?
    • G = (V, T, N, S, P)
    • V- Vocabulary, all symbols that can be used in the alphabet of the language, numbers letters etc.
    • T - Terminals
    • N - Non terminals,
    • S - Starting symbol
    • P - Production Rules
  4. What is a terminal and non terminal symbol?
    Terminals, can not be broken down further, such as a letter or a number.

    Non-terminal symbols are placeholders for patterns of terminal symbols that can be generated by the non terminal symbols.

    "Word" and "verb" both are stings but "verb" has a different significant meaning within the language and is in a separate class from the terminals that are only "words".
  5. What is a deriviation?
    That is when you can go from one expression to another through using the rules of the language.
  6. What is the difference between a direct derivation an a "simple" derivation?
    Let w0=lz0r (in other word w0 is the concatenation of l, z0, and r)
    If there is only one step between the starting and end point, with an arrow => we say there is a direct derivation and if there are multiple steps we say it is derivable.
  7. What does the question what is the language of mean?
    It means the all possible strings considering the grammars rules and its vocabulary. So basically all the answers possible to produce by the language.
  8. Image Upload 1
    Image Upload 2
  9. Image Upload 3
    Image Upload 4
  10. Image Upload 5
    Image Upload 6
  11. Image Upload 7
    Image Upload 8
Card Set
1.1.1 Phrase-structure Grammars
Matte plugg