Theory of Computing : Context-Free Language

sigma = {b, c, d}, L = {w: #_b (w) greaterthanorequalto #_c (w) greaterthanorequalto #_d (w) greaterthanorequalto 0}. Compute the hybrid proof below showing that L notelementof CFLs. a L' = L intersection b* c* d*. If L elementof CFLs then L' elementof CFLs because .. b Use the CF Pumping Theorem to show that L' notelementof CFLs. b Let w = b^K c^K d^K. w elementof L' and | w | greaterthanorequalto K. b. ii Divide w into three regions b^K c^K d^K 1 | 2 | 3 b. iii If either v or y cross regions .. b. iv The possibilites for (m, n) are .. b. v The values of (m, n) that are not allowed by the guarantee that | vxy | lessthanorequalto K are .. b. vi therefore L' notelementof CFLs because .. c. therefore L notelementof CFLs because .. sigma = {b, c, d}, L = {w: #_b (w) greaterthanorequalto #_c (w) greaterthanorequalto #_d (w) greaterthanorequalto 0}. Compute the hybrid proof below showing that L notelementof CFLs. a L' = L intersection b* c* d*. If L elementof CFLs then L' elementof CFLs because .. b Use the CF Pumping Theorem to show that L' notelementof CFLs. b Let w = b^K c^K d^K. w elementof L' and | w | greaterthanorequalto K. b. ii Divide w into three regions b^K c^K d^K 1 | 2 | 3 b. iii If either v or y cross regions .. b. iv The possibilites for (m, n) are .. b. v The values of (m, n) that are not allowed by the guarantee that | vxy | lessthanorequalto K are .. b. vi therefore L' notelementof CFLs because .. c. therefore L notelementof CFLs because