Context Free Grammar

5 Key excerpts on "Context Free Grammar"

• 

  eBook - ePub

  Theory of Computation Simplified

  Simulate Real-world Computing Machines and Problems with Strong Principles of Computation (English Edition)

  • Dr. Varsha H. Patil, Dr. Vaishali S. Pawar, Dr. Swati A. Bhavsar, Dr. Aboli H. Patil(Authors)
  • 2022(Publication Date)
  • BPB Publications

    (Publisher)

  (a + b)^d/e + (S – T)

  S → (a + b)^d/e + (T – V)

  S → (a + b)^d/e + (V – F)

  S → (a + b)^d/e + (F – I)

  S → (a + b)^d/e + (I – F)

  S → (a + b)^d/e + (– F),

  Hence, proved.

  Conclusion

  In this chapter, we learnt the basic elements of grammar and it definition. The Context Free Grammar is a way of describing languages by using production rules. Derivations and languages are generated by using the start symbol and a string of terminals is derived by repeatedly replacing it by the body of production rules. While replacing, if we replace the leftmost non-terminal, then the resulting derivation is leftmost, else if we replace the rightmost non-terminal, then the resulting derivation is rightmost. We also learnt the concept of ambiguous grammar and how to remove ambiguity form it. Then we learnt the representation of grammar in two types of normal forms such as Chomsky normal form and Greibach normal form. Further, the types of grammar were studied using Chomsky hierarchy. At the end of the chapter, we learnt the applications of Context Free Grammar.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Automata and Computability

  A Programmer's Perspective

  • Ganesh Gopalakrishnan(Author)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  7

  The basic goal of designing a CFG is to come up with an elegant set of rules that are intuitively correct, and (upon being challenged) rigorously shown to be consistent and complete. Many such proofs can be elegantly structured around a rather nice picture which we call the “hill/valley” plot.8

  Example: For our illustration, consider a different language, namely Leqab , which is exactly the set of all strings that contain an equal number of a ’s and b ’s. We can derive a CFG for it by growing the language inside-out.9 More specifically,

  •  ε is in the language, and therefore we must include a production of the form S -> ″

  •  Now, we set up the pattern aSbS , and think inductively in our minds; we also indicate the questions that naturally arise:

  –  If S is consistent, then placing an equal amount of a ’s and b ’s keeps it consistent.

  –  But do we settle for aSb or aSbS ? We choose the latter, as it does not force a b -ending.

  –  Do we include bSaS ? We feel it is necessary, to avoid an a -only ending.

  –  Do we throw in an SS case? While doing so won’t cause inconsistency, it may be unnecessary for completeness (see below).

  Let us assume we don’t need the SS case, and present the CFG designed thus far:

  S -> ’’ | aSbS | bSaS

  We now prove that this CFG is consistent, and the SS production is not necessary (the CFG is complete with respect to Leqab

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Artificial Intelligence

  With an Introduction to Machine Learning, Second Edition

  • Richard E. Neapolitan, Xia Jiang(Authors)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)
• A set of terminal symbols. These are the words in the language such as “block”, “on”, “speak”, and “operator”.
• A set of nonterminal symbols. These symbols represent linguistic concepts that categorize phrases in the language such as NounP hrase and V erbP hrase.
• A start symbol. This symbol represents the entire string being parsed. For the English language, it is S entence.
• A set of derivation rules. The nonterminal symbol on the left in these rules can be substituted by the terminal and nonterminal symbols on the right. For example, if we write “Noun → block,” then a Noun can be substituted by block.
• The “|” denotes “or”.
Such a grammar is a context-free grammar (CFG) , which means that there may only be one nonterminal symbol on the left in each rule. Table 16.1 shows a simple CFG grammar.
Table 16.1 A CFG
A grammar is in Chomsky normal form if every rule is of the form A B C or D word, where A , B , C , and D are nonterminals and “word” is a terminal. The context-free grammar in Table 16.1 is not in Chomsky normal form because of rules 2, 3, 6 and 10 through 15. It is possible to show that every context-free grammar can be transformed into a grammar that is in Chomsky normal form.
The terminals are the words in the language, and the set of all of them is called the lexicon . The grammar in Table 16.1 shows a very small lexicon for illustration. Most grammars we would actually use would have a much larger lexicon. A legal sentence is a string of symbols that can be derived using a sequence of these rules. A derivation must start with the start symbol Sentence, perform a sequence of substitutions by applying the rules, and end up with the sentence being parsed.
Example 16.1 Suppose we want to derive the following sentence:
the monkey reads a book.
The following is a derivation of this sentence using the grammar in Table 16.1 .
■
A derivation can be represented by a parse tree . Each non-leaf in the tree contains the nonterminal symbol on the left of a rule used in the derivation, and each of its children contains one of the terminal or nonterminal symbols on the right of the rule. Each leaf contains a terminal symbol. The root of the tree is the start symbol Sentence . Figure 16.2