Alphabet, string, language — formal definitions: Question bank

Recall Symbols & rules used on this sheet (skim before you start)

This practice sheet is self-contained — here is every symbol it uses, in one place.

== $Σ$ == (Sigma) — an alphabet: a finite, non-empty set of atomic symbols, e.g. ${0, 1}$ .
== $ε$ == (epsilon) — the empty string: a string with zero symbol-positions, $∣ ε ∣ = 0$ . It is a string, never a symbol of $Σ$ .
== $∣ w ∣$ == — the length of string $w$ = number of symbol-positions in it.
== $Σ^{k}$ == — the set of all strings of length exactly $k$ . Fact: $∣ Σ^{k} ∣ = ∣Σ ∣^{k}$ , and $Σ^{0} = {ε}$ .
== $Σ^{*}$ == (Kleene star) $= ⋃_{k \geq 0} Σ^{k}$ — all finite strings, including $ε$ .
== $Σ^{+}$ == (Kleene plus) $= ⋃_{k \geq 1} Σ^{k}$ — all strings of length $\geq 1$ , excluding $ε$ .
== $L$ == — a language: any subset of $Σ^{*}$ , i.e. a (possibly infinite) set of strings.
== $\emptyset$ == — the empty language: a set with zero strings, $∣ \emptyset ∣ = 0$ . (Not the same as ${ε}$ , which has one string!)
Concatenation of languages: $L_{1} L_{2} = {x y : x \in L_{1}, y \in L_{2}}$ (all glued pairs, as a set).
Powers: $L^{0} = {ε}$ , $L^{k} = L^{k - 1} L$ ; and $L^{*} = ⋃_{k \geq 0} L^{k}$ .
Complement over $Σ$ : == $\overline{L} = Σ^{*} ∖ L$ == — every string not in $L$ .

True or false — justify

The empty string

ε

belongs to every alphabet

Σ

False.

ε

is a string (length 0) living on the String floor; an alphabet contains symbols on the Alphabet floor. Every alphabet's

Σ^{*}

contains

ε

, but

Σ

itself never does.

Figure — Alphabet, string, language — formal definitions

\emptyset

and

{ε}

are the same language.

False.

\emptyset

has zero strings (

∣ \emptyset ∣ = 0

);

{ε}

has one string, the empty one (

∣ {ε} ∣ = 1

). Empty box vs. box holding one blank sheet — see the box diagram below.

Σ^{*}

is uncountable, like the real numbers in

[0, 1]

False.

Σ^{*}

holds only finite strings, so we can shortlex-list them (length 0, then length 1, then length 2, …), giving every string a definite position — a bijection with

N

, hence countable. A real in

[0, 1]

needs an infinite digit-string, which no such list reaches. See the two figures below.

Concatenation of strings is commutative:

x y = y x

always.

False.

01 \neq = 10

— position order is part of a string's identity. Concatenation is associative and has identity

ε

, but not commutative.

For any alphabet,

Σ^{*} = Σ^{+} \cup {ε}

True.

Σ^{+}

(the plus) is every string of length

\geq 1

; adding back the single length-0 string

ε

gives all finite strings, which is

Σ^{*}

. And

ε \in / Σ^{+}

, so the union genuinely adds one new element.

\emptyset^{*} = \emptyset

False. By the power rule

L^{*} = ⋃_{k \geq 0} L^{k}

and

L^{0} = {ε}

is included for every

L

. So even when

L = \emptyset

, the

k = 0

term contributes

{ε}

: thus

\emptyset^{*} = {ε}

. See the union-strip figure below.

A language must be a finite set of strings.

False. A language is any subset of

Σ^{*}

, so it may be infinite (e.g. all even-length strings) — the definition places no size restriction.

Every language over

Σ

is a subset of

Σ^{*}

True. That is the definition of "language":

L \subseteq Σ^{*}

. Restrictions like "regular" or "context-free" come later to classify which

L

a machine can recognise — see Regular Languages.

∣ ε ∣ = 1

because

ε

is one string.

False.

∣ w ∣

counts symbol-positions, not strings.

ε

has no positions, so

∣ ε ∣ = 0

. "One string" is a fact about the set

{ε}

(size 1), not about the length.

ε x = x

for every string

x

True.

ε

is the identity of concatenation ("do nothing" string), so gluing it on either side changes nothing:

ε x = x ε = x

An alphabet may be infinite as long as it is non-empty.

False. An alphabet must be finite and non-empty. Concretely: a DFA has a finite transition table with one outgoing edge per symbol from each state; if

Σ = {a_{1}, a_{2}, a_{3}, \dots}

were infinite, each state would need infinitely many edges — the table can never be written down, so the finite-machine model collapses.

Spot the error

Σ = {}

is a perfectly good alphabet — it's just small."

The error is allowing the empty set.

Σ

must be non-empty; with no symbols you could write nothing, so

Σ^{*} = {ε}

only — a useless theory with exactly one possible input.

"Since

\emptyset

accepts nothing and

{ε}

accepts nothing meaningful, both have size 0."

{ε}

has size 1 — it contains the empty string as a member. Only

\emptyset

has size 0. Counting the box's contents,

{ε}

holds one item (a blank sheet).

\emptyset L = {ε}

because concatenating with 'nothing' leaves

L

alone."

Wrong:

\emptyset L = \emptyset

. Recall

L_{1} L_{2} = {x y : x \in L_{1}, y \in L_{2}}

; here there is no

x \in \emptyset

to pick, so no pair — hence no string — is produced. The identity for concatenation is

{ε}

, not

\emptyset

{ε} L = \emptyset

since

ε

is empty."

Wrong:

{ε} L = L

. Using

L_{1} L_{2} = {x y}

with

x = ε

and every

y \in L

gives

ε y = y

, reproducing all of

L

{ε}

is the multiplicative identity.

"The string

011

is the same as the language

{0, 1, 1}

— same symbols."

Two errors.

011

is an ordered string on the String floor;

{0, 1, 1}

is a set (a Language) and equals

{0, 1}

since sets ignore order and duplicates. Order and repetition matter for strings, never for sets.

∣ Σ^{0} ∣ = 0

because there are no length-0 strings."

Wrong:

∣ Σ^{0} ∣ = ∣Σ ∣^{0} = 1

. There is exactly one length-0 string,

ε

, over any alphabet. So

Σ^{0} = {ε}

L_{1} L_{2} = {0, 01, 011, 01}

for

L_{1} = {0, 01}, L_{2} = {1, ε}

— four products."

The four products (

0 \cdot 1 = 01

0 \cdot ε = 0

01 \cdot 1 = 011

01 \cdot ε = 01

) are right, but

L_{1} L_{2}

is a set; the duplicate

01

collapses to one. Correct:

{0, 01, 011}

Because a language is exactly "the set of inputs we accept," and at the definition stage we impose no constraint. Constraints (regular, context-free) come later to sort which languages machines like a DFA can recognise.

Why must an alphabet be finite?

A machine reading input must be able to react to every possible symbol. A finite

Σ

lets a finite machine handle every case; an infinite

Σ

never could.

Why is

Σ^{*}

countable even though it is infinite?

Every string is finite in length, so we can order them shortlex — length 0, then length 1, then length 2… — a complete list with a definite position for each. That listing is a bijection with the natural numbers

N

Why does the set of all languages

2^{Σ^{*}}

end up uncountable even though

Σ^{*}

is countable?

Taking the power set of a countably infinite set gives an uncountable set (Cantor's diagonal argument). This is the seed of undecidability — more languages exist than machines to recognise them. See Countability and Diophantine Diagonalization.

Why does concatenation make

(Σ^{*}, concat)

a monoid but not a group?

It is associative and has identity

ε

(monoid). But no non-empty string has an inverse: once

∣ x y ∣ = ∣ x ∣ + ∣ y ∣ \geq 1

, you can never concatenate back down to

ε

. No inverses ⇒ not a group.

Why does the reversal

w^{R}

always satisfy

∣ w^{R} ∣ = ∣ w ∣

Reversal only re-orders positions; it adds and removes nothing. It's a bijection on the same positions, so the count is unchanged.

Why must

\emptyset^{*}

include

ε

even though

\emptyset

has no strings?

Because

L^{*} = ⋃_{k \geq 0} L^{k}

starts at $k = 0$ , and

L^{0}

is defined as

{ε}

for every language (it means "zero copies concatenated = the empty word"). The

k = 0

slice contributes

{ε}

regardless of

L

; every later slice

\emptyset^{k}

(

k \geq 1

) is empty. Union:

{ε} \cup \emptyset \cup \emptyset \cup \dots = {ε}

Edge cases

ε

a substring of every string

w

Yes. Take

w = x ε z

with

x = ε, z = w

; the empty string sits between any two positions. It is also a prefix and a suffix of everything.

ε \in L

when

L = {w : ∣ w ∣ is even}

Yes.

∣ ε ∣ = 0

and

0

is even. The tempting "no string ⇒ not in a length-language" ignores that

0

is a legitimate even number.

What is

Σ^{*}

when

Σ = {a}

(single symbol)?

The infinite set

{ε, a, aa, aaa, \dots}

— one string of each length. A single-symbol alphabet is valid (finite, non-empty) and still generates infinitely many strings.

Can

w^{0}

ever be anything other than

ε

No. By definition

w^{0} = ε

for every string

w

, even

w = ε

itself. "Repeat zero times" leaves the blank word, matching

∣ w^{0} ∣ = 0 \cdot ∣ w ∣ = 0

Is the complement

\overline{\emptyset}

over

Σ

equal to

Σ^{*}

Yes. By definition

\overline{L} = Σ^{*} ∖ L

, so removing nothing leaves everything:

\overline{\emptyset} = Σ^{*}

. Dually

\overline{Σ^{*}} = \emptyset

L = {ε}

, what is

L^{*}

Still

{ε}

. Every power

L^{k}

concatenates copies of

ε

, which produces only

ε

, so the union collapses to

{ε}

Does

Σ^{k}

include

ε

for any

k

Only for

k = 0

Σ^{0} = {ε}

. For every

k \geq 1

Σ^{k}

holds strings of length exactly

k

, so

ε

(length 0) is excluded.

Question bank — Alphabet, string, language — formal definitions

True or false — justify

Spot the error

Why questions

Edge cases