Computer Science 456/656 Worksheet - 2013
ADVERTISEMENT
1
2
3
4
5Computer Science 456/656 Spring 2013
Practice for the First Examination, February 28, 2013
The entire practice examination is 455 points.
The real exam will be much
shorter.
1. True or False. [5 points each]
(a)
Every subset of a regular language is regular.
m
n
(b)
Let L be the language over Σ = {a, b} consisting of all strings of the form a
, where
b
m, n ≥ 0. Then L is a regular language.
(c)
The complement of every regular language is regular.
(d)
The Kleene closure of every context-free language is context-free.
(e)
If a language has an unambiguous context-free grammar, then it is is accepted by some
deterministic push-down automaton.
(f)
If a language has an ambiguous context-free grammar, then it is is not accepted by any
deterministic push-down automaton.
(g)
There is a PDA that accepts all valid C++ programs.
(h)
The intersection of any two regular languages is regular.
(i)
The language consisting of all base 7 numerals for positive integers n such that n % 3 = 2
is regular.
(j)
The intersection of any two context-free languages is context-free.
m
n
m
(k)
Let L be the language over Σ = {a, b} consisting of all strings of the form a
, where
b
c
m, n ≥ 0. Then L is a context-free language.
m
n
(l)
Let L be the language over Σ = {a, b} consisting of all strings of the form a
b
, where
m ≥ n. Then L is a context-free language.
(m)
The complement of every context-free language is context-free.
(n)
The union of any two context-free languages is context-free.
(o)
If a language has an context-free grammar, then it is is accepted by some push-down au-
tomaton.
(p)
Every context-free language has an unambiguous context-free grammar.
(q)
Every language that has an unambiguous context-free grammar is accepted by some DPDA.
(r)
The intersection of any two context-free languages is context-free.
(s)
Every deterministic machine is a non-deterministic machine.
(t)
The language consisting of all base 2 numerals for integer powers of 2 is regular.
(u)
There is a DPDA that accepts the language of all palindromes over the binary alphabet
{0, 1}.
1
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education