- +1-530-264-8006
- info@tutorsglobe.com

18,76,764

Questions

Asked

21,311

Experts

9,67,568

Questions

Answered

Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!

Submit Assignment
## Closure Properties of Class of CFLs, Context Free Grammars & Languages

Closure properties of class of CFLs:: The class of CFLs over an alphabet A is closed beneath the regular operations union, catenation and Kleene star.Theorem (CFL closure properties)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.

: The class of CFLs over an alphabet A is not closed beneath intersection and is not closed beneath implement.TheoremWe 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 = {0

^{m}1^{m}2^{n}| m, n ≥ 1} and L1 = {0^{m}1^{n}2^{n}| m, n ≥ 1}.L0 ∩ L1 = {0

^{k}1^{k}2^{k}| 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(n

^{3}) by means of dynamic programmingCasually, 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.

: L = {0Illustration^{k}1^{k}| 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 AssistanceTutors, at the

www.tutorsglobe.com, take pledge to provide full satisfaction and assurance inTheory of Computation helpviaonline tutoring. Students are getting 100% satisfaction byonline tutorsacross the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email basedTheory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. ThroughOnline Tutoring, you would be able to complete your homework or assignments at your home. Tutors at theTutorsGlobeare committed to provide the best qualityonline tutoringassistance forTheory of Computation Homework helpandassignment helpservices. 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.TutorsGlobeassure 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 thehomework helpas per the deadline or given instruction by the student, we refund the money of the student without any delay.