M2 | Languages, Encoding, Theorems, and Proofs

An alphabet, often denoted by Σ, is…

A finite set

Which of the following is a string over the alphabet Σ = {a, b, c, ..., z}?

ε

True or False:

A string is a finite sequence of symbols drawn from an alphabet.

True – Strings are made up of symbols from a defined alphabet.

Which of the following is NOT a valid string? Assuming that an alphabet is:

Σ = {a, b, c, ..., z}

1a2b

True or False:

If Σ = {a, b, c, d}, does the string “abcdedcba” belong to that alphabet?

False – The string contains letters outside the alphabet.

True or False:

If Σ = {0, 1}, does the string “010101011” belong to that alphabet?

True – The string only uses symbols 0 and 1.

True or False:

If Σ = {0, 1}, does the string “000000” belong to that alphabet?

True – Only symbols from Σ appear in the string.

What does Σ* (sigma star) represent?

The set of all possible strings over an alphabet including ε

If Σ = {a, b}, which of the following belongs to Σ*?

aa

True or False:

Σ+ (sigma plus) represents the set of all possible strings over an alphabet excluding ε.

True – Σ+ contains all strings of length ≥ 1.

If Σ = {a, b}, which of the following does not belong to Σ+?

ε

How is the length of a string written?

|w|

What is the length of the string “0101110”?

7

What is the length of the empty string ε?

0

If w is a string over an alphabet Σ that has length n, and we write w = w1w2…wn where each wi ∈ Σ, what does w ∉ Σ mean?

w is not a string over the alphabet Σ

What is the reversal of a string w?

The string obtained by writing w in the opposite order

If w = w1w2…wn, how is the reversed string written?

wnwn−1…w1

What does concatenation of strings x and y produce?

The string xy, obtained by appending y to the end of x

If x has length m and y has length n, what is the length of xy after concatenation?

m + n

When is a string S a substring of a string T?

If S occurs contiguously as part of T

True or False:

If S = “aaa” and T = “aabbaa”, S a substring of T

False

If S = “abb” and T = “aabbaa”, is S a substring of T?

Yes

What makes S a proper substring of T?

S is a substring of T and S ≠ T

When is a string S a prefix of T?

If S precedes T

What makes S a proper prefix of T?

S is a prefix of T and S ≠ T

When is a string S a suffix of T?

If S comes after T

True or False:

The empty string ε is a prefix or suffix of every string.

True - because ε occurs at the start or end of any string

What is a language in formal language theory?

A finite or infinite set of strings over an alphabet

If Σ = {a, b}, which of the following is a possible language over Σ?

{ε, a, b, aa, ab, ba, bb, aaa, ...}

True or False:

∅, {ε}, {a, b} can all be languages over Σ

True – This is true because all these are sets of strings over Σ

Which of the following is not a valid language over Σ = {a, b}?

{c, a, aa, aaa, aaaa, aaaaa, ...}

True or False:

Languages are sets, so union, intersection, and set difference can produce new languages.

True - because all these operations on sets result in sets of strings, which are languages

If L1 = {a, b} and L2 = {b, c}, what is L1 ∪ L2?

{a, b, c}

If L1 = {a, b} and L2 = {b, c}, what is L1 ∩ L2?

{b}

Let Σ = {a, b}. Which of the following strings belongs to L1 = {strings with b’s and an even number of a’s}?

b

Which of the following describes L1 ∪ L2?

Let L1 = {strings with b’s and an even number of a’s}
Let L2 = {strings with no b’s}

All strings that contain b's and an even number of a’s plus strings of just a's

True or False:

Let L1 = {strings with b’s and an even number of a’s}
Let L2 = {strings with no b’s}

L1 ∩ L2 = {ε, aa, aaaa, aaaaaa, ...}

True

Which of the following describes L2 − L1?

Let L1 = {strings with b’s and an even number of a’s}
Let L2 = {strings with no b’s}

{a, aaa, aaaaa, aaaaaaa, ...}

True or False:

Let L1 = {strings with b’s and an even number of a’s}
Let L2 = {strings with no b’s}

¬(L2 − L1) = {strings with at least one b} ∪ {strings with an even number of a's}

True

Which of the following correctly describes the concatenation L1 L2?

Let L1 = {cat, dog, mouse, bird}

Let L2 = {bone, food}

{catbone, catfood, dogbone, dogfood, mousebone, mousefood, birdbone, birdfood}

True or False:

Concatenation of two languages L1 and L2 always produces strings that are members of L1 or L2.

True

If L1 = {cat, dog} and L2 = {bone, food}, which string is in L1L2?

catbone

True or False:

L1L2 = L2L1

False

What is included in the Kleene star L* if
L = {dog, cat, fish}?

dogcatfish

True or False:

L* always contains the empty string ε.

True - L* includes all concatenations, including zero concatenations.

Which of the following is in L+ if
L = {dog, cat, fish}?

dog

True or False:

L+ always contains the empty string ε.

False - L+ contains concatenations of one or more elements from L, so ε is never included.

Given an alphabet Σ, the number of different languages L over Σ is given by:

|Σ|

True or False:

If Σ = ∅, then Σ* = {ε} where Σ* is the largest language
over the alphabet Σ

True - even the empty alphabet produces the empty string.

The set P(Σ*) denotes:

The set of all subsets of Σ*

True or False:

If Σ = {a, b}, then |P(Σ*)| is finite.

False - Σ* is infinite, so its power set is also infinite.

If Σ ≠ ∅, the set of languages over Σ is:

Uncountably infinite

True or False:

If Σ ≠ ∅, then Σ* is uncountably infinite.

False - Σ* is countably infinite; only its power set is uncountably infinite

P(Σ*) is uncountably infinite because:

Cantor’s theorem states that the power set of a countably infinite set is uncountably infinite

True or False:

If Σ = {0,1}, then there exists a bijection between P(Σ*) and the real numbers ℝ.

True

True or False:

Defining a language for a decision problem only requires including the inputs for which the answer is “no.”

False - it should include exactly the inputs for which the answer is “yes”

True or False:

Every decision problem can be represented as a language over some alphabet.

True

If L = {aaa}, is x = aaa in L?

Yes

If L = {aaa}, is y = aba in L?

No

True or False:

If both x and y are in L, then we can conclude x = y.

True - membership in L ensures both strings are identical

True or False:

Encoding strings into a language L is a method used to solve decision problems.

True

For problems that are not already decision problems, what must we do first?

Reformulate the problem as a decision problem

True or False:

Encoding a problem as a language recognition task allows us to check solutions using string membership.

True

Example: Given a list of integers, sort it

In the example of sorting a list, how is the problem encoded?

By examining a pair of lists and checking if the second is the sorted version of the first

True or False:

The encoding of a non-decision problem as a language recognition task always produces multiple languages.

False

Which of the following strings belongs to the language
L = { w1#w2 | w2 is a sorted version of w1 }?

1, 5, 3, 9, 6#1, 3, 5, 6, 9

True or False:

In L, w2 can contain elements not present in w1.

False

How is the problem of executing a database query encoded for language recognition?

By transforming the query and expected reply into a string in a language

True or False:

Evaluating a reply in a language allows us to check correctness of the query result.

True

Which of the following strings belongs to the language
L = { d#q#a | a is the correct result of applying q to d }?

(name, age, phone), (John, 23, 567-1234), (Mary, 24, 234-9876)#(SELECT name FROM . WHERE age = 23)#(John)

True or False:

Let L = { d#q#a | d is an encoding of a database, q is a
string representing a query, and a is the correct result
of applying q to d}

In L, the query string q must exactly match the database encoding d to be valid.

False

What does the language L = { d#q#a } represent in terms of database queries?

Encodings of databases, queries, and correct results

True or False:

Let L = { d#q#a | d is an encoding of a database, q is a
string representing a query, and a is the correct result
of applying q to d}

Any string in L automatically guarantees that the query result a is correct for d and q.

True

Is a mathematical statement proved true

Theorems

Statements that are proven primarily to help prove another, more important statement are called…

Lemmas

Statements that can be easily concluded from a proven theorem are called…

Corollaries

What theorem is this?

Corollaries

A proof in mathematics is…

A convincing logical argument that a statement is true

To prove that (A∪B)′ = A′∩B′, we start by showing that…

Every element of one set is also an element of the other and vice versa

If x∈A′∩B′, which of the following is true?

x∉A and x∉B

Mathematical proofs often contain multiple subproofs because:

Each subproof can have a different type of argument

True or False:

A proof in the theory of computation usually contains just one type of argument.

True

The reason for describing different types of arguments in proofs is:

Certain types occur frequently in computation theory

A proof may include several types of arguments because:

Each type handles a different case or subproblem

A theorem that claims a certain type of object exists can be proven by:

Showing how to construct the object

True or False:

A proof by construction demonstrates existence by providing a method to create the object.

True

The reasoning that assumes a statement is false and derives an obviously false consequence is called:

Proof by contradiction

Jack sees Jill, who has just come in from outdoors. On observing that she is completely dry, he knows that it is not raining

In the Jack and Jill example, why does Jack conclude that it is not raining?

Because assuming it is raining leads to a contradiction (Jill would be wet, but she is dry)

True or False:

Proof by contradiction can only be used in mathematics, not in everyday reasoning.

False

Proof by induction is used to:

Show that all elements of an infinite set have a specified property

True or False:

Proof by induction can be applied to verify that a program works correctly for all possible inputs.

True

An example application of proof by induction is:

Showing that an arithmetic expression computes correctly for every assignment to its variables

True or False:

Proof by induction is only applicable to numerical expressions, not programs or logical statements.

False