CS 475 Midterm: CS 475 Alabama Fall2017 Exam2 1Solutions
Document Summary
You may choose any set of problems that adds up to 100 or more points: write all the strings of length 6 that are generated by this context-free grammar. Solution a parse tree for each such string. [30 points for cs 475] [20 points for cs 575] X e c y f: write all the strings of lengths 3 and 6 that are accepted by this pushdown automaton. Hint: first get the strings of length 3, then use these to get the strings of length 6. [30 points for cs 475] [20 points for cs 575] a, /t b, /u c, /vw f, v/ g, w/ h, x/ . , z0/ e, / j, t/ k, / . Alternatively, write an ambiguous cfg for this language. Hint: the number of a"s must be either more or less than the number of b"s. S atbs | bvas | ax | by.