Assignment Help - homework help

  Closure Properties of Class of CFLs, Context Free Grammars & Languages

Closure properties of class of CFLs:

Theorem (CFL closure properties): The class of CFLs over an alphabet A is closed beneath the regular operations union, catenation and Kleene star.

Proof: Given that CFLs L, L’ ⊆ A*, consider any grammars G, G’ which produce L and L’, correspondingly. Join G and G’ suitably to get grammars for L ∪ L’, L L’, and L*. Example: when G = (V, A, P, S), we get G(L*) = (V ∪ {S0}, A, P ∪ { S0 -> S S0 ,  S0 ->  ε }, S0).

The proof above is equivalent to the proof of closure of class or regular languages beneath union, catenation and Kleene star. There we joined two FAs to a single one employing series, parallel and loop combinations of FAs. However beyond the three regular operations, the analogy stops. For regular languages, we confirmed closure beneath complement by appealing to deterministic FAs as acceptors. For such, modifying all the accepting states to non-accepting, and vice-versa, outcomes the complement of language accepted. This reasoning drops for CFL’s, as deterministic PDAs accept merely a subclass of CFLs. For non-deterministic PDAs, modifying accepting states to non-accepting, and vice-versa, does not generate the complement of language accepted. Certainly, closure beneath complement doesn’t hold for CFLs.

Theorem: The class of CFLs over an alphabet A is not closed beneath intersection and is not closed beneath implement.

We verify this theorem in two manners: First, by exhibiting two CFLs whose intersection is probably not CF and second by exhibiting the CFL whose complement is probably not CF.

Pf ∩:  Let consider CFLs L0 = {0m 1m 2n | m, n ≥ 1} and L1 = {0m 1n 2n | m, n ≥ 1}.

L0 ∩ L1 = {0k 1k 2k | k ≥ 1} is not CF, as we verified previously by using the pumping lemma.

This entails that the class of CFLs is not closed beneath complement. If it were, it would as well be closed beneath intersection, since of the identity:  L ∩ L’ = ¬(¬L  ∪  ¬L’ ).  However we as well prove this outcome in a direct way by exhibiting the CFL L whose complement is not context free. L’s complement is notorious language L2 = {w w / w ∈ {0, 1}}, that we have proven not context free by using the pumping lemma.

Pf ¬:  We illustrate that L = {u | u is not of the form u = w w} is context free by showing a CFG for L:

  S -> Y | Z | Y Z | Z Y
  Y -> 1 | 0 Y 0 | 0 Y 1 | 1 Y 0 | 1 Y 1
  Z -> 0 | 0 Z 0 | 0 Z 1 | 1 Z 0 | 1 Z 1

The productions for Y produce all odd strings, that sis, strings of odd length, with 1 as its center symbol.

Analogously, Z produces all the odd strings with a 0 as its center symbol. The odd strings are not of the form u = w w, therefore they are involved in L by the productions S -> Y | Z. Now we illustrate that the strings u of even length which are not of the form u = w w are accurately such of the form Y Z or Z Y.

At first, consider a word of the form Y Z, like the catenation of y = 1 1 0 1 0 0 0 and z = 1 0 1, where the center 1 of y and center 0 of z are highlighted. Writing y z = 1 1 0 1 0 0 0 1 0 1 as catenation of the two strings of equivalent length, namely 1 1 0 1 0 and 0 0 1 0 1, exhibits that the former center symbols 1 of y and 0 of z contain both become the 4-th symbol in their relevant strings of length 5. Therefore, they are a witness pair whose clash exhibits that y z ≠ w w for any w. This and the analogous condition for Z Y, illustrate that the set of strings of form Y Z or Z Y are in L.

On contrary, consider any even word u = a1 a2 .. aj .. ak b1 b2 .. bj .. bk that is not of the form u = w w. There exists an index j where aj ≠ bj, and we can take all of aj and bj as center symbol of its own odd string. The given illustration shows a clashing pair at index j = 4: u = 1 1 0 0 1 1 1 0 1 1. Now u = 1 1 0 0 1 1 1 0 1 1 can be written as u = z y, here z = 1 1 0 0 1 1 1   ∈ Z and y = 0 1 1 ∈ Y.

The given figure how the different string lengths labeled α and β add up.

282_closure properties of cfl.jpg

The word ‘problem’. CFL parsing in time O(n3) by means of dynamic programming

Casually, the word problem asks:  Given G and w ∈ A*, decide whether w ∈ L(G).

More accurately: Is there an algorithm which applies to any grammar G in certain given class of grammars, and any w ∈ A*, to decide whether w ∈ L(G)?

Most of the algorithms resolve the word problem for CFGs, example: i) Convert G to Greibach NF and enumerate all the derivations of length ≤ |w| to see whether any of them produces w; or ii) Construct an NPDA M which accepts L(G), and feed w to M.

Illustration:  L = {0k 1k | k ≥ 1}. G: S -> 01 | 0 S1.  Use ‘0’ as a stack symbol to count the number of 0s.

1336_closure properties of cfl_1.jpg

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
Home | Company Overview | Services | Discover Q&A | Sitemap | Contact Us | T & C | Refund Policy | Copyright Policy | Blog | Q&A | Directory

©TutorsGlobe All rights reserved 2022-2023.