56. Given R is a relation
{
}
R
a b a
b
= ( , )
divides
on the set of positive
integers. Determine
(a) R
–1
(b) R
57. Determine whether the relation R on the set of all integers is reflexive,
symmetric, antisymmetric, and/or transitive, where ( , )
x y R
∈ if and
only if
(a) xy ≥1 (b) x y
b
≡ (mod ) (c) x y
=
2
58. Determine the language of grammar G given by V = {S, A, a, b},
T = {a, b} and production P
S
aA S
b A aa
= →
→
→
{
,
,
}.
59. Determine the grammar that generates the set
{
, , ,
}
0 1
0 1 2
n n
n =
KK .
60. Determine at least two grammars that generate the set {0 1
m n
m and n
are nonnegative integers}.
61. Determine the grammar that generates the set
{
, , ,
}
0 1 2
0 1 2
n n n
n =
KK
62. Determine the grammar for each of the following languages.
(a) set of all bit strings containing an even number of 0
s and no 1
s .
(b) set of all strings containing more 0
s than 1
s .
(c) set of all strings containing an equal number of 0
s and 1
s .
(d) set of all strings containing an unequal number of 0
s and 1
s .
63. Determine the grammars for the following languages on Σ = { }
a .
(a) L = {w : | w | mod 3 = 0}
(b) L = {w : | w | mod 3 ≥ | w | mod 2}
64. Assuming Σ = { , }
a b with n a (w) and n b (w) as the number of a’s and b’s
respectively in string w, find grammars for
(a) L w n w
n w
a
b
=
=
{ : ( )
( )}
2
(b) L w n w n w
a
b
=
>
{ : ( )
( )}
65. Are the two grammars with respective productions
S
aSb ab
→
| | λ
and
S
aAb ab
A aAb
→
→
|
| λ
equivalent?
66. Are there languages for which L L
*
*
= ?
67. Prove that (
)
L L
L L
R
R R
1 2
2 1
=
for all languages L 1 and L 2 .
68. Show that any 2 2
n
n
× chessboard with one square removed can be tiled
50
Theory of Automata, Formal Languages and Computation