Question: 3 0 points ) You are ( still ) working on a fantasy novel. For the dwarves, you have decided to create a language over

30 points) You are (still) working on a fantasy novel. For the dwarves, you have decided to create a language over the alphabet ={k, u, d, z, e, f } with the following rules: Words that start with k cannot end with an f. u can not come directly after z, k or f. e can only come directly after z, d or u. Words must have more short letters (us, es, and zs) than tall letters (ks, ds, and fs) The number of fs and us combined must be the same as the number of zs and es combined.Show that this language is not context-free using the pumping lemma for context-free languages, by following these steps:(a)(5 points) Construct a valid word w of length at least n (you do not know what n is!).(b)(15 points) Determine all possible, valid ways, that w can be split into the five parts uxyzv.(c)(10 points) Show that none of these possible splits can be pumped (if x and z are repeated a certain number of times, or removed entirely, the word will become invalid).

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!