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.
Millman Theorem and Nortons Theorem tutorial all along with the key concepts of Calculation of a Norton equivalent circuit, Ohm's Law and Reciprocity
tutorsglobe.com conditions of perfect competition assignment help-homework help by online perfect competition tutors
tutorsglobe.com significance of photosynthesis assignment help-homework help by online photosynthesis tutors
www.tutorsglobe.com offers solved linear programming questions, sample assignments lp questions and answers, development of lp problems, and steps to solve lp questions.
tutorsglobe.com limitations of two kingdom system assignment help-homework help by online kingdom system of classification tutors
The statement of cash flows is a fairly current addition to the annual published financial statements. Companies were only needed to publish a statement of financial position (balance sheet) and an income statement.
solvation of alkali metal ions tutorial all along with the key concepts of solvated electrons, cmplexation behaviour of alkali metals, anomalous natures of lithium
tutorsglobe.com parasites assignment help-homework help by online nutrition in fungi tutors
stop the anxiety of complicated assignments and get first-class international law and organization assignment help to score high!
Get the optimum E-Business Assignment Help service from top experts at low prices and excel your academic grades!
Dielectrics and Capacitors tutorial all along with the key concepts of Capacitance and Permittivity, Parallel Plate capacitor, Energy of a Charged Capacitor, Energy Density, Combination of Capacitors, Capacitors in Parallel, Capacitors in Series and Types of Capacitor
The accomplishment of an inter-firm’ comparison scheme relies on the successful operation of uniform costing system. The comparison would be futile and farce without Uniform Costing.
theory and lecture notes of ttl inverter all along with the key concepts of circuit structure of ttl, logical operation of ttl, transfer characteristic of ttl and noise margins. tutorsglobe offers homework help, assignment help and tutor’s assistance on ttl inverter.
alkanoic acids tutorial all along with the key concepts of characteristics of alkanoic acids, oxidation of primary alkanols and uses of alkanoic acids
purification methods-empirical and molecular formula tutorial all along with the key concepts of purification methods, distillation, crystallization, chromatography, empirical and molecular formula, structural formula
1932992
Questions Asked
3689
Tutors
1440459
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!