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.
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.
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.
what is international trade? define some of basis of international trade, www.tutorsglobe.com offers theory and concepts of international trade, assignment help - international trade homework help.
tutorsglobe.com european history before 1715 assignment help-homework help by online history tutors
tutorsglobe.com scheduling assignment help-homework help by online operating system tutors
tutorsglobe.com quality choice assignment help-homework help by online imperfect information tutors
www.tutorsglobe.com offers design documentation homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Fate of Organic Matter in Sedimentary Basins tutorial all along with the key concepts of Accumulation of Organic Matter, Diagenesis, Catagenesis, Metagenesis, Transformation of Organic Matter and Kerogen to Petroleum
the material control is guaranteed through laying down proper methods for storing, purchasing, issuing and minimizing material losses through identifying slow moving, obsolete, dormant material and also through minimizing scrap, wastages, spoilages and defectives.
tutorsglobe.com types of aestivation assignment help-homework help by online aestivation tutors
www.tutorsglobe.com offers decomposition and modularity homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
tutorsglobe.com infections due to salmonella assignment help-homework help by online salmonella tutors
Theory and lecture notes of Distributed transaction management all along with the key concepts of distributed transaction management, transaction management. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Distributed transaction management.
Electrical Properties Associated with Rocks tutorial all along with the key concepts of Electric Current Methods, Resistivity and Conductivity, Electrical resistivities of rocks and minerals, Apparent resistivity, Overburden effects
tutorsglobe.com baroque art assignment help-homework help by online humanities tutors
tutorsglobe.com metabolism of proteins assignment help-homework help by online protein metabolism tutors
tutorsglobe.com objectives of fiscal policy assignment help-homework help by online fiscal policy tutors
1949511
Questions Asked
3689
Tutors
1476412
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!