8/29 - Languages

Question 1

Let A and B be two languages over the same alphabet.

What is the union of A and B defined as?

Answer 1

The union of A and B is defined as

A ∪ B = {w: w ∈ A or w ∈ B}.

Question 2

Let A and B be two languages over the same alphabet.

What is the concatenation of A and B defined as?

Answer 2

AB = {ww′ : w ∈ A and w′ ∈ B}.
In words, AB is the set of all strings obtained by taking an arbitrary string w in A and an arbitrary string w′ in B, and gluing them together (such that w is to the left of w′).

Question 3

Let A and B be two languages over the same alphabet.

What is the star of A defined as?

Answer 3

A^∗ = {u1u2 … uk : k ≥ 0 and ui ∈A for all i=1, 2,…,k}.
In words, A^∗ is obtained by taking any finite number of strings in A, and gluing them together. Observe that k = 0 is allowed; this corresponds to the empty string Ee. Thus, Ee ∈ A^∗.

Question 4

Star in the language of A (A^*)

Answer 4

Define A^0 = {Ee},
and, for k ≥ 1,
A^k = AA^(k-1),
i.e., A^k is the concatenation of the two languages A and A^(k−1). Then we have
A^∗ = (inf//U//k=0) A^k.
// means on top of (visual description)