.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :title: Context-Free Grammars Part 1
   :author: Mostafa Mohammed; Cliff Shaffer
   :institution: Virginia Tech
   :satisfies:
   :topic: Context-Free Grammars and Languages
   :keyword: Context-Free Grammar; Context-Free Language
   :naturallanguage: en
   :programminglanguage: N/A
   :description: Introduction to context-free languages and gramamrs.

Context-Free Grammars Part 1
============================

Context-Free Languages 
----------------------

In previous chapters, we saw that some languages are regular
languages, which means that we can define a DFA, NFA that recognizes
that language, or we can represent it with a regular
expression or regular grammar.
Here are a few examples of regular languages:

* keywords in a programming language
* names of identifiers
* integers
* a finite list of miscillaneous symbols such as :math:`=`.

We also know that some languages are non-regular, and we learned how
to use tools like the Pumping Lemma to prove a given language is
non-regular.
Examples of non-regular languages include:

* :math:`\{a^ncb^n\ |\ n > 0\}`
* mathematical expressions like :math:`((a + b) - c)`
* block structures for programming languages (:math:`\{\}` in Java/C++
  and ``begin`` ... ``end`` in Pascal)
* Balanced parentheses

Now we will look at a class of languages that is larger than the class
of regular languages, called
:term:`context-free languages <context-free language>`
or :term:`CFG`.
Perhaps not surprisingly, a CFL is any language that can be
represented by a :term:`context-free grammar` or :term:`CFG`.

.. inlineav:: CFLFS ff
   :links: AV/PIFLA/CFL/CFLFS.css
   :scripts: DataStructures/FLA/FA.js DataStructures/PIFrames.js AV/PIFLA/CFL/CFLFS.js
   :output: show
   :keyword: Context-Free Grammars and Languages


String Derivation
-----------------

.. inlineav:: CFGDerivationsFS ff
   :links: AV/PIFLA/CFL/CFGDerivationsFS.css
   :scripts: DataStructures/FLA/FA.js DataStructures/PIFrames.js AV/PIFLA/CFL/CFGDerivationsFS.js
   :output: show
   :keyword: Context-Free Grammars and Languages


Derivation Trees
----------------

.. inlineav:: DerivationTreesFS ff
   :links: AV/PIFLA/CFL/DerivationTreesFS.css
   :scripts: DataStructures/FLA/FA.js DataStructures/FLA/PDA.js DataStructures/PIFrames.js AV/PIFLA/CFL/DerivationTreesFS.js
   :output: show
   :keyword: Context-Free Grammars and Languages

Derivation Trees Example
------------------------

.. inlineav:: TreeExampleCON ss
   :links: AV/PIFLA/CFL/TreeExampleCON.css
   :scripts: lib/underscore.js DataStructures/FLA/FA.js DataStructures/FLA/PDA.js AV/PIFLA/CFL/TreeExampleCON.js
   :output: show
   :keyword: Context-Free Grammars and Languages


Practice question 1
-------------------

.. avembed:: Exercises/FLA/NumParseTreeNodes.html ka
   :long_name: Determine Number of nodes
   :keyword: Context-Free Grammars and Languages


Membership Problem
------------------

.. inlineav:: MembershipFS ff
   :links: AV/PIFLA/CFL/MembershipFS.css
   :scripts: DataStructures/FLA/FA.js DataStructures/PIFrames.js AV/PIFLA/CFL/MembershipFS.js
   :output: show
   :keyword: Context-Free Grammars and Languages


Practice question 2
-------------------

.. avembed:: Exercises/FLA/StringGenFromGmr.html ka
   :long_name: String Generated By a Grammar
   :keyword: Context-Free Grammars and Languages