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.
tutorsglobe.com portal of entry assignment help-homework help by online non-toxic determinants of virulence tutors
www.tutorsglobe.com offers aldehydes and ketones homework help, aldehydes and ketones assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
TutorsGlobe.com Control and Subsidiary Account Assignment Help-Homework Help by Online T - Accounts Tutors
tutorsglobe.com silver nitrate assignment help-homework help by online compound tutors
Managers are generally needed to make several estimates while preparing financial Statements. These estimates might require revision in the light of new information.
in this type of machine (fully automatic machine) there is only one tub that works as the washer, rinse also the drier.
Reflection at Plane Surfaces tutorial all along with the key concepts of Laws of reflection, Formation of Image by Plane Mirror, Image Formed by Plane Mirror, second law of reflection
www.tutorsglobe.com offers reaction classification homework help, reaction classification assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
The procedure of adjusting tuned circuits and settings the variable capacitors to enhance the selectivity and sensitivity of the receiver is known as alignment.
tutorsglobe.com fresh water crisis and management assignment help-homework help by online environmental science tutors
www.tutorsglobe.com offers Layering homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
www.tutorsglobe.com offers system fundamentals homework help, system fundamentals assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Simple Experimental design-Analysis of Variance tutorial all along with the key concepts of Types of Experimental Design, Completely Randomized Design, Randomized Block Design, Simple Factorial Experiment, Analysis of Variance, Assumptions in ANOVA and Hypotheses in ANOVA
In the integrated accounting system, various set of accounts within cost accounting and financial accounting systems are not maintained.
tutorsglobe.com biosynthesis of phospholipids assignment help-homework help by online phospholipids tutors
1957778
Questions Asked
3689
Tutors
1458326
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!