.. _CFLProp:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "CFLProp";ODSA.SETTINGS.MODULE_LONG_NAME = "Properties of Context-Free Languages";ODSA.SETTINGS.MODULE_CHAPTER = "modules"; ODSA.SETTINGS.BUILD_DATE = "2019-07-03 11:58:01"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


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

.. avmetadata::
   :author: Susan Rodger and Cliff Shaffer
   :requires: Context-Free Languages
   :satisfies:
   :topic: Finite Automata

Properties of Context-Free Languages 
====================================

Properties of Context-Free Languages 
------------------------------------

.. note::
   
   We will not cover Theorem 8.2

Which of the following languages are CFL?

* :math:`L = \{a^nb^nc^j \mid 0 < n\le j\}`

  .. note::

     NOT CFL 
* :math:`L = \{a^nb^ja^nb^j \mid n>0, j>0\}`

  .. note::

     NOT CFL 

* :math:`L = \{a^nb^ja^kb^p \mid n+j \le k+p, n>0, j>0, k>0, p>0 \}`

  .. note::

     CFL 

* :math:`L = \{a^nb^ja^jb^n \mid n>0, j>0\}`

  .. note::

     CFL 

**Pumping Lemma for Regular Languages**

Let :math:`L` be a regular language,
then there is a constant :math:`m` such that :math:`w\in L`,
:math:`|w|\ge m`, :math:`w = xyz` such that 

   * :math:`|xy| \le m`
   * :math:`|y| \ge 1`
   * for all :math:`i\ge 0, xy^iz \in L`

We were able to show that :math:`a^nb^n` is not a regular language. 


**Pumping Lemma for CFL's**

Let :math:`L` be any infinite CFL.
Then there is a constant :math:`m` depending only on :math:`L`,
such that for every string :math:`w` in :math:`L`, 
with :math:`|w| \ge m`, we may partition :math:`w = uvxyz` such that:

   | :math:`|vxy| \le m`, (limit on size of substring)
   | :math:`|vy| \ge 1`,  (:math:`v` and :math:`y` not both empty)
   | For all :math:`i \ge 0, uv^ixy^iz \in L`

**Proof:** (sketch)

There is a CFG :math:`G` such that :math:`L = L(G)`.

Consider the parse tree of a long string in :math:`L`.

For any long string, some nonterminal :math:`N` must appear twice in
the path.

.. odsafig:: Images/lt8ptree1.png
   :width: 400
   :align: center
   :capalign: justify
   :figwidth: 90%
   :alt: lt8ptree1

| :math:`N \stackrel{*}{\Rightarrow} vNy` and
  :math:`N \stackrel{*}{\Rightarrow} x`. 
| :math:`S \stackrel{*}{\Rightarrow} uNz \stackrel{*}{\Rightarrow} uvNyz 
  \stackrel{*}{\Rightarrow} uvxyz`
| By repeating the :math:`v` and :math:`y` subtrees, get 
  :math:`N \stackrel{*}{\Rightarrow} v^iNy^i \stackrel{*}{\Rightarrow} v^ixy^i`.

.. odsafig:: Images/lt8ptree2.png
   :width: 400
   :align: center
   :capalign: justify
   :figwidth: 90%
   :alt: lt8ptree2

QED 

.. topic:: Example

   Consider :math:`L = \{a^nb^nc^n: n\ge 1\}`.
   Show :math:`L` is not a CFL.

**Proof:** (by contradiction)

   | Assume :math:`L` is a CFL and apply the pumping lemma.
   | Let :math:`m` be the constant in the pumping lemma and consider 
     :math:`w = a^mb^mc^m`.
     Note :math:`|w|\ge m`.
   | Show there is no division of :math:`w` into :math:`uvxyz` such
     that :math:`|vy|\ge 1`, :math:`|vxy|\le m`, and
     :math:`uv^ixy^iz \in L` for :math:`i = 0, 1, 2, \ldots`.
   |
   | **Case 1:** Neither :math:`v` nor :math:`y` can contain 2 or more
     distinct symbols.
     If :math:`v` contains :math:`a` 's and :math:`b` 's,
     then :math:`uv^2xy^2z \notin L` since there will be :math:`b` 's
     before :math:`a` 's.
   | Thus, :math:`v` and :math:`y` can be only :math:`a` 's,
     :math:`b` 's, or :math:`c` 's (not mixed). 
   |
   | **Case 2:** :math:`v = a^{t_1}`, then :math:`y = a^{t_2}`
     or :math:`b^{t_3} (|vxy| \le m)`
   | If :math:`y = a^{t_2}`,
     then :math:`uv^2xy^2z = a^{m+t_1+t_2}b^mc^m \notin L` since 
     :math:`t_1 + t_2 > 0, n(a) > n(b)` (number of :math:`a` 's is
     greater than number of :math:`b` 's) 
   | If :math:`y = b^{t_3}`, then
     :math:`uv^2xy^2z = a^{m+t_1}b^{m+t_3}c^m \notin L`
     since :math:`t_1 + t_3 > 0`, either :math:`n(a) > n(c)` or
     :math:`n(b) > n(c)`.
   |
   | **Case 3:** :math:`v = b^{t_1}`, then :math:`y = b^{t_2}` or :math:`c^{t_3}`.
   | If :math:`y = b^{t_2}`, then :math:`uv^2xy^2z = a^mb^{m+t_1+t_2}c^m \notin L` 
     since :math:`t_1 + t_2 > 0, n(b) > n(a)`. 
   | If :math:`y = c^{t_3}`, then
     :math:`uv^2xy^2z = a^mb^{m+t_1}c^{m+t_3} \notin L` 
     since :math:`t_1 + t_3 > 0`, either :math:`n(b) > n(a)` or
     :math:`n(c) > n(a)`.
   |
   | **Case 4:** :math:`v = c^{t_1}`, then :math:`y = c^{t_2}`.
   | Then, :math:`uv^2xy^2z = a^mb^mc^{m+t_1+t_2} \notin L`
     since :math:`t_1 + t_2 > 0, n(c) > n(a)`.
   |
   | Thus, there is no breakdown of :math:`w` into :math:`uvxyz` such
     that :math:`|vy| \ge 1`, :math:`|vxy| \le m` and for all
     :math:`i\ge 0`, :math:`uv^ixy^iz` is in :math:`L`.
   | This is a contradiction, thus, :math:`L` is not a CFL. Q.E.D.


.. topic:: Example

   Why would we want to recognize a language of the type
   :math:`\{a^nb^nc^n: n\ge 1\}`?
 
   Recognize underlined words:
 
   :math:`\underline{word}` is stored as
   :math:`word\beta\beta\beta\beta\ \_\ \_\ \_\ \_`
   where :math:`\beta` represents a backspace. 

.. topic:: Example

   Consider :math:`L = \{a^nb^nc^p : p > n > 0 \}`.
   Show that :math:`L` is not a CFL.
 
  **Proof:**

     | Assume :math:`L` is a CFL and apply the pumping lemma.
       Let :math:`m` be the constant in the pumping lemma and consider 
       :math:`w = a^mb^mc^{m+1}`. 
       Note: :math:`|w| \ge m`.
     | Show that there is no division of :math:`w` into :math:`uvxyz`
       such that :math:`|vy| \ge 1`, 
       :math:`|vxy| \le m`, and :math:`uv^ixy^iz \in L` for
       :math:`i = 0, 1, 2, \ldots`.
     |
     | **Case 1:** Neither :math:`v` nor :math:`y` can contain 2 or more
       distinct symbols.
       If :math:`v` contains a's and b's, then :math:`uv^2xy^2z \notin L`
       since there will be b's before a's. 
     | Thus, :math:`v` and :math:`y` can be only a's, b's, or c's (not mixed).
     | 
     | **Case 2:** :math:`v = a^{t_1}`, then :math:`y = a^{t_2}` or
       :math:`b^{t_3} (|vxy| \le m)`  
     | If :math:`y = a^{t_2}`, then
       :math:`uv^2xy^2z = a^{m+t_1+t_2}b^mc^{m+1} \notin L` 
       since :math:`t_1 + t_2 \ge 1, n(a) > n(b)`. 
     | If :math:`y = b^{t_3}`, then
        :math:`uv^2xy^2z = a^{m+t_1}b^{m+t_3}c^{m+1} \notin L` 
        since :math:`t_1 + t_3 \ge 1`, either :math:`n(c)` is not
        :math:`> n(a)` or :math:`n(c)` is not :math:`> n(b)`. 
     | 
     | **Case 3:** :math:`v = b^{t_1}`, then :math:`y = b^{t_2}` or
       :math:`c^{t_3}`.
     | If :math:`y = b^{t_2}`, then
       :math:`uv^2xy^2z = a^mb^{m+t_1+t_2}c^{m+1} \notin L`
       since :math:`t_1 + t_2 \ge 1, n(b) > n(a)`. 
     | If :math:`y = c^{t_3}`, then
       :math:`uv^0xy^0z = a^mb^{m-t_1}c^{m+1-t_3} \notin L`
       since :math:`t_1 + t_3 \ge 1`, either :math:`n(b) < n(a)`
       or :math:`n(c)` is not :math:`> n(a)`. 
     | 
     | **Case 4:** :math:`v = c^{t_1}`, then :math:`y=c^{t_2}`.
     | Then, :math:`uv^0xy^0z = a^mb^mc^{m+1 -t_1-t_2} \notin L`
       since :math:`t_1 + t_2 \ge 1, n(c)` is not :math:`> n(a)`. 
     |
     | Thus, there is no breakdown of :math:`w` into :math:`uvxyz`
       such that :math:`|vy| \ge 1, |vxy| \le m` and for all
       :math:`i\ge 0, uv^ixy^iz` is in :math:`L`. 
     | Contradiction, thus, :math:`L` is not a CFL. Q.E.D. 

.. topic:: Example

   Consider :math:`L = \{a^jb^k: k = j^2\}`.
   Show :math:`L` is not a CFL.
 
   **Proof:**

      | Assume :math:`L` is a CFL and apply the pumping lemma.
        Let :math:`m` be the constant in the pumping lemma and consider 
        :math:`w = a^mb^{m^2}`. 
      | Show there is no division of :math:`w` into :math:`uvxyz` such
        that :math:`|vy| \ge 1, |vxy| \le m`, and
        :math:`uv^ixy^iz \in L` for :math:`i = 0, 1, 2, \ldots`.
      |
      | **Case 1:** Neither :math:`v` nor :math:`y` can contain 2 or more
        distinct symbols.
        If :math:`v` contains a's and b's, then
        :math:`uv^2xy^2z \notin L` since
        there will be b's before a's.
      | Thus, :math:`v` and :math:`y` can be only a's, and then b's (not mixed).
      |
      | **Case 2:** :math:`v = a^{t_1}`, then :math:`y = a^{t_2}` or
        :math:`b^{t_3}`.  
      | If :math:`y=a^{t_2}`, then
        :math:`uv^2xy^2z = a^{m+t_1+t_2}b^{m^2} \notin L`
        since :math:`0 < t_1 + t_2 \le m`, not enough b's. 
      | If :math:`y=b^{t_3}`, then
        :math:`uv^2xy^2z = a^{m+t_1}b^{m^2+t_3} \notin L` since
        :math:`0 < t_1 + t_3 \le m`, if :math:`t_1 = 0`, too many b's.
        If :math:`t_1 = 1`, :math:`(m+1)^2 = m^2 +2m+1`,
        so for :math:`t_1\ge 1`, there will be too few b's. 
      | 
      | **Case 3:** :math:`v=b^{t_1}`, then :math:`y = b^{t_2}`.
      | Then, :math:`uv^2xy^2z = a^mb^{m^2 + t_1 + t_2} \notin L`
        since :math:`t_1 + t_2 > 0`, not enough a's. 
      |
      | Thus, there is no breakdown of :math:`w` into :math:`uvxyz`
        such that :math:`|vy| \ge 1`,
        :math:`|vxy| \le m` and for all :math:`i \ge 0, uv^ixy^iz` is
        in :math:`L`.
      | Contradiction, thus, :math:`L` is not a CFL. Q.E.D. 

.. topic:: Exercise

   Prove the following is not a CFL by applying the 
   pumping lemma. (Answer is at the end of this handout). 

      | :math:`L = \{ a^{2n}b^{2p}c^nd^p : n,p \ge 0 \}`.

.. topic:: Example

   Consider :math:`L = \{w{\bar w}w : w\in \Sigma^*\}, \Sigma = \{a, b\}`, 
   where :math:`\bar w` is the string :math:`w` with each occurence of
   :math:`a` replaced by :math:`b` and each occurence of :math:`b` 
   replaced by :math:`a`.
   For example, :math:`w = baaa, {\bar w} = abbb, w{\bar w} = baaaabbb`.
   Show :math:`L` is not a CFL.
 
   Proof:
      | Assume :math:`L` is a CFL and apply the pumping lemma.
        Let :math:`m` be the constant in the pumping lemma and consider 
        :math:`w = a^mb^ma^m`. 
      | Show there is no division of :math:`w` into :math:`uvxyz` such
        that :math:`|vy| \ge 1`, :math:`|vxy| \le m`, and
        :math:`uv^ixy^iz \in L` for :math:`i = 0, 1, 2, \ldots`.
      | (Note: :math:`v` and :math:`y` could be mixed a's and b's and
        still be in the language).
      | (Note: I will use a to represent the a's in the front of
        :math:`w` and :math:`A` to represent the a's at the end of
        :math:`w` when it is not clear.)
      | 
      | **Case 1:** :math:`v = a^{t_1}`, then
        :math:`y=a^{t_2}, b^{t_3}` or :math:`a^{t_2}b^{t_3}`.
      | If :math:`y=a^{t_2}`, then
        :math:`uv^2xy^2z = a^{m+t_1+t_2}b^ma^m \notin L`
        since :math:`t_1+t_2 > 0`, more a's on left than on right. 
      | If :math:`y=b^{t_3}`, then
        :math:`uv^2xy^2z = a^{m+t_1}b^{m+t_3}a^m \notin L`
        since :math:`t_1 + t_3 > 0`, either more a's on left than on
        right, or more b's than a's on the right. 
      | If :math:`y = a^{t_2}b^{t_3}`, then
        :math:`uv^0xy^0z = a^{m-t_1-t_2}b^{m-t_3}a^m \notin L`
        since :math:`t_1 + t_2 + t_3 > 0`, either number of a's on
        left and right not equal, or number of b's not equal to number
        of a's on right.
      | 
      | **Case 2:** :math:`v=a^{t_1}b^{t_2}`, then :math:`y=b^{t_3}`.
        Then :math:`uv^0xy^0z = a^{m -t_1}b^{m-t_2-t_3}a^m \notin L`
        since :math:`t_1 + t_2 + t_3 > 0`, either number of a's on
        left and right not equal, or number of b's not equal to number
        of a's on right.
      | 
      | **Case 3:** :math:`v = b^{t_1}`, then :math:`y=b^{t_2}, A^{t_3}`,
        or :math:`b^{t_2}A^{t_3}`.
      | If :math:`y = b^{t_2}`, then
        :math:`uv^2xy^2z = a^mb^{m+t_1+t_2}a^m \notin L`
        since :math:`t_1+t_2 > 0`, :math:`n(b) \neq n(a)` on either side. 
      | If :math:`y=A^{t_3}`, then
        :math:`uv^2xy^2z = a^mb^{m+t_1}a^{m+t_3} \notin L`
        since :math:`t_1 + t_3 > 0`, either :math:`n(a)` on left and
        right not equal, or :math:`n(b)` not equal to number of a's on left. 
      | If :math:`y=b^{t_2}A^{t_3}`, then
        :math:`uv^0xy^0z = a^mb^{m-t_1-t_2}a^{m-t_3} \notin L`
        since :math:`t_1 + t_2 + t_3 > 0`, either :math:`n(a)` on left
        and right not equal, or :math:`n(b)` not equal to number of a's on left. 
      |  
      | **Case 4:** :math:`v = b^{t_1}A^{t_2}`, then :math:`y = A^{t_3}`.
      | Then :math:`uv^0xy^0z = a^mb^{m-t_1}a^{m-t_2-t_3} \notin L`
        since :math:`t_1 + t_2 + t_3 > 0`, either :math:`n(a)` on left
        and right not equal, or :math:`n(b)` not equal to number of a's on left. 
      | 
      | **Case 5:** :math:`v=A^{t_1}`, then :math:`y=A^{t_2}`.
      | Then :math:`uv^0xy^0z = a^mb^ma^{m-t_1 -t_2} \notin L`
        since :math:`t_1+t_2 > 0`, :math:`n(a)` on left not equal to
        :math:`n(a)` on right.
      |
      | Thus, there is no breakdown of :math:`w` into :math:`uvxyz`
        such that :math:`|vy| \ge 1`,  
        :math:`|vxy| \le m` and for all :math:`i \ge 0`,
        :math:`uv^ixy^iz` is in :math:`L`.  
      | Contradiction, thus, :math:`L` is not a CFL. Q.E.D. 

.. topic:: Example

   Consider :math:`L = \{a^nb^pb^pa^n\}`.
   :math:`L` is a CFL. The pumping lemma should apply!

   Let :math:`m \ge 4` be the constant in the pumping lemma.
   Consider :math:`w = a^mb^mb^ma^m`.

   We can break :math:`w` into :math:`uvxyz`, with:

      :math:`u = a^mb^{m-2} \qquad v = b \qquad x = bb \qquad y = b \qquad z = b^{m-2}a^m`
  
   Thus, :math:`|vy| \ge 1, |vxy| \le m`, and for all
   :math:`i \ge 0, uv^ixy^iz = a^mb^{m+i}b^{m+i}a^m \in L`.
 
   If you apply the pumping lemma to a CFL, then you should find a partition 
   of :math:`w` that works! 

   .. note::

      This is not a proof that a language is CFL! Why not?


(Chap 8.2) Closure Properties of CFLs
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Example: :math:`L=\{a^nb^n | n>0\}`,
:math:`L\circ L = \{a^nb^na^mb^m | n>0, m>0 \}`

.. topic:: Theorem

   CFL's are closed under union, concatenation, and star-closure.

   **Proof:**

      Given 2 CFG :math:`G_1 = (V_1,T_1,S_1,P_1)`  and
      :math:`G_2 = (V_2,T_2,S_2,P_2)`

      | * Union:
      |   Construct :math:`G_3` such that :math:`L(G_3) = L(G_1) \cup L(G_2)`.
      |   :math:`G_3 = (V_3,T_3,S_3,P_3)`
      |   :math:`V_3 = V_1 \cup V_2 \cup \{S_3\}, T_3 = T_1 \cup T_2`, and 
          :math:`P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1 | S_2 \}`.

      | * Concatenation:
      |   Construct :math:`G_3` such that
          :math:`L(G_3) = L(G_1) \circ L(G_2)`.
      |   :math:`G_3 = (V_3,T_3,S_3,P_3)`
      |   :math:`V_3 = V_1 \cup V_2 \cup \{S_3\}, T_3 = T_1 \cup T_2`, and 
          :math:`P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1S_2 \}`.

      | * Star-Closure
      |   Construct :math:`G_3` such that :math:`L(G_3) = L(G_1)^*`
      |   :math:`G_3 = (V_3,T_3,S_3,P_3)`
      |   :math:`V_3 = V_1 \cup \{S_3\}, T_3 = T_1`, and 
          :math:`P_3 = P_1 \cup P_2 \cup \{S_3 \rightarrow S_1S_3|\lambda \}`.

      QED. 


.. topic:: Theorem

   CFL's are NOT closed under intersection and complementation.

   **Proof:**

      | * Intersection:
      |   Let :math:`L_1 = \{a^nb^nc^m | n,m > 0\}` and
          :math:`L_2 = \{a^nb^mc^m | n,m> 0\}`
      |   :math:`L_1` and :math:`L_2` are CFLs 
      |   Then :math:`L_1 \cap L_2 = \{a^nb^nc^n | n >0 \}` is not CFL. 

      | * Complementation:
      |   Set identity: 

        .. math::
           
           L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}

      .. note::

         Show Venn Diagram! 

   Thus, CFLs are not closed under complementation. 

.. note::

   Example for theorem below:

   | :math:`L_1 = \{a^nb^ma^n | m> 0, n>0 \}`
   | :math:`L_2 = \{w | w \in{\Sigma}^{*}` and :math:`w` has an even
     number of b's}, :math:`\Sigma = \{a,b\}`,
   | :math:`L_1 \cup L_2 = \{a^nb^mb^ma^n\}` is a CFL. 

.. topic:: Theorem

   CFL's are closed under *regular* intersection. 
   If :math:`L_1` is CFL and :math:`L_2` is regular,
   then :math:`L_1 \cap L_2` is CFL.

   **Proof:** (sketch)  

      | This proof is similar to the construction 
        proof in which we showed regular languages are closed under intersection. 
        We take a NPDA for :math:`L_1` and a DFA for :math:`L_2` and
        construct a NPDA for :math:`L_1 \cap L_2`.
      | :math:`M_1 = (Q_1,\Sigma, \Gamma, {\delta}_1, q_0, z, F_1)`
        is an NPDA such that :math:`L(M_1) = L_1`.
      | :math:`M_2 = (Q_2,\Sigma, {\delta}_2, q_0^{'}, F_2)` is a DFA
        such that :math:`L(M_2) = L_2`.
      | Construct NPDA :math:`M_3 = (Q_3,\Sigma, \Gamma, {\delta}_3,
                              (q_0,q_0^{'}), z, F_3)`
        where :math:`Q_3 = Q_1 \times Q_2`, and
        :math:`F_3 = \{(q,p) | q\in F_1, p\in F_2\}`.
      | Example of replacing arcs (NOT a Proof!):

      .. odsafig:: Images/lt10inter.png
         :width: 400
         :align: center
         :capalign: justify
         :figwidth: 90%
         :alt: lt10inter

      Note this is not a proof, but sketches how we will combine the DFA and NPDA. 
      We must formally define :math:`{\delta}_3`. If

         | :math:`(q_k,x) \in {\delta}_1(q_i,a,b)`
         | :math:`\delta_2(q_j^{'},a) = q_l^{'}`

      then 

         | :math:`((q_k,q_l^{'}),x) \in {\delta}_3((q_i,q_j^{'}),a,b)`

      Must show

         | :math:`((q_0,q_0^{'}),w,z) \stackrel{*}{\vdash} ((q_i,q_j^{'}),\lambda,x)`
         | :math:`(q_i,q_j^{'})\in F_3`

      if and only if

         | :math:`(q_0,w,z) \stackrel{*}{\vdash} (q_i,\lambda,x)`
         | :math:`(q_0^{'},w) \stackrel{*}{\vdash} (q_j^{'},\lambda)`
         | :math:`q_i \in F_1` and :math:`q_j^{'}\in F_2`

      Must show: 

         | w \in L(M_3)` iff :math:`w \in L(M_1)` and :math:`w \in L(M_2)`. 

      QED. 

      NOTE: Why doesn't this proof work for if we try to construct an 
      NPDA that represents the intersection of two NPDA's? Need 2 stacks.

**Questions about CFL:**

   | 1. Decide if CFL is empty?
   |    Know how to get rid of useless variables and productions, if there is 
        anything left, then CFL is not empty. 

   | 2. Decide if CFL is infinite?
   |    Get rid of useless variables and productions, :math:`\lambda`-rules, and 
        unit productions.
        Then if there is a variable that repeats :math:`A \stackrel{*}{\Rightarrow} xAy`,
        then :math:`L` is infinite. 

     .. note::

        What type of language is a grammar that has this property?
        How do we recognize it automatically?
        
.. topic:: Example

   Consider :math:`L = \{ a^{2n}b^{2m}c^nd^m : n,m \ge 0 \}`.
   Show :math:`L` is not a CFL.

   **Proof:**
      | Assume :math:`L` is a CFL and apply the pumping lemma.
        Let :math:`m` be the constant in the pumping lemma and
        consider :math:`w = a^{2m}b^{2m}c^md^m`.
      | Show there is no division of :math:`w` into :math:`uvxyz` such
        that :math:`|vy| \ge 1`, :math:`|vxy| \le m`,
        and :math:`uv^ixy^iz \in L` for :math:`i = 0, 1, 2, \ldots`.
      |
      | **Case 1:** Neither :math:`v` nor :math:`y` can contain 2 or
        more distinct symbols.
        If :math:`v` contains a's and b's, then
        :math:`uv^2xy^2z \notin L` since
        there will be b's before a's.
      | Thus, :math:`v` and :math:`y` can be only a's, b's, c's, or d's (not mixed).
      | 
      | **Case 2:** :math:`v = a^{t_1}`, then :math:`y = a^{t_2}`
        or :math:`b^{t_3} (|vxy| \le m$)`.
      | If :math:`y = a^{t_2}`, then
        :math:`uv^2xy^2z = a^{2m+t_1+t_2}b^{2m}c^md^m \notin L`
        since :math:`t_1 + t_2 > 0`, the number of a's is not twice the number of c's.
      | If :math:`y=b^{t_3}`, then :math:`uv^2xy^2z = a^{2m+t_1}b^{2m+t_3}c^md^m \notin L`
        since :math:`t_1 + t_3 > 0`, either the number of a's (:math:`n(a)`) is
        not twice :math:`n(c)` or :math:`n(b)` is not twice :math:`n(d)`.
      |
      | **Case 3:** :math:`v = b^{t_1}`, then :math:`y = b^{t_2}` or
        :math:`c^{t_3}`.
      | If :math:`y=b^{t_2}`, then :math:`uv^2xy^2z = a^{2m}b^{2m+t_1+t_2}c^md^m \notin L`
        since :math:`t_1 + t_2 > 0, n(b) > 2 * n(d)`.
      | If :math:`y = c^{t_3}`, then
        :math:`uv^2xy^2z = a^{2m}b^{2m+t_1}c^{m+t_3}d^m \notin L`
        since :math:`t_1 + t_3 > 0`, either :math:`n(b) > 2*n(d)`
        or :math:`2*n(c) > n(a)`.
      | 
      | **Case 4:** :math:`v = c^{t_1}`, then :math:`y = c^{t_2}` or
        :math:`d^{t_3}`.
      | If :math:`y = c^{t_2}`, then
        :math:`uv^2xy^2z = a^{2m}b^{2m}c^{m+t_1+t_2}d^m \notin L`
        since :math:`t_1 + t_2 > 0, 2 * n(c) > n(a)`.
      | If :math:`y = d^{t_3}`, then
        :math:`uv^2xy^2z = a^{2m}b^{2m}c^{m+t_1}d^{m+t_3} \notin L`
        since :math:`t_1 + t_3 > 0`, either :math:2*n(c) > n(a)`
        or :math:`2*n(d) > n(b)`.
      |
      | **Case 5:** :math:`v = d^{t_1}`, then :math:`y = d^{t_2}`.
      | Then :math:`uv^2xy^2z = a^{2m}b^{2m}c^md^{m+t_1+t_2} \notin L`
        since :math:`t_1 + t_2 > 0, 2*n(d) > n(c)`.
      |
      | Thus, there is no breakdown of :math:`w` into :math:`uvxyz`
        such that :math:`|vy| \ge 1`,
        :math:`|vxy| \le m` and for all :math:`i\ ge 0`,
        :math:`uv^ixy^iz` is in :math:`L`.
      | Contradiction, thus, :math:`L` is not a CFL. Q.E.D.