This is an open book exam. You are allowed to consult only Sudkamp text
during the exam.
1 Mathematical Induction (5 pts)
Prove that 12 + 22 + . . . + n
2 = n(n + 1)(2n + 1)/6 for n > 0.
2 Regular Sets (1 + 2 + 2 pts)
Let S = {0, 1}. Is the intersection of the regular sets {0}* and {1}* empty?
Give an example of an infinite regular set over S whose complement is finite.
Give an example of an infinite regular set over S whose complement is infinite.
3 Regular Expressions (4 pts)
Give a regular expression for the language over {a, b} whose strings do not
contain the substring ab.
4 Context-Free Grammars (6 pts)
Give a context-free grammar for the following language:
{a
i
b
i+j
c
j
d
k
| 0 = i ? 0
5 Context-Free Grammars (5 pts)
Use set notation to describe the language associated with the following grammar.
S -> aSB | aB
B -> bb | b
6 Regular Grammars (5 pts)
Construct a regular grammar for the language associated with the following
grammar.
S -> aSB | /\
B -> bB | /\
Wright State University Department of Computer Science and Engineering CS 466/666 Spring 2011 Prasad First Midterm (30 pts) This is an open book exam. You are allowed to consult only Sudkamp text during the exam. 1 Mathematical Induction (5 pts) Prove that 12 + 22 + . . . + n2 = n(n + 1)(2n + 1)/6 for n > 0. 2 Regular Sets (1 + 2 + 2 pts) Let Σ = {0, 1}. Is the intersection of the regular sets {0}∗ and {1}∗ empty? Give an example of an infinite regular set over Σ whose complement is finite. Give an example of an infinite regular set over Σ whose complement is infinite. 3 Regular Expressions (4 pts) Give a regular expression for the language over {a, b} whose strings do not contain the substring ab. 4 Context-Free Grammars (6 pts) Give a context-free grammar for the following language: {aibi+jcjdk | 0 ≤ i ∧ 0 < j="" ∧="" 0="">< k}.="" 5="" context-free="" grammars="" (5="" pts)="" use="" set="" notation="" to="" describe="" the="" language="" associated="" with="" the="" following="" grammar.="" s="" -=""> aSB | aB B -> bb | b 6 Regular Grammars (5 pts) Construct a regular grammar for the language associated with the following grammar. S -> aSB | /\ B -> bB | /\ 1