2. Languages

Question 1

Alphabet

Answer 1

any non-empty finite set Σ

Question 2

Symbols

Answer 2

members of the alphabet

Question 3

String

Answer 3

finite sequence of symbols

ε = empty string

Question 4

Examples of strings over the alphabet {0,1}

Answer 4

over this alphabet = strings in this alphabet

ε, 0, 11001111000101…

Question 5

String Length

Answer 5

NOT set cerdinality
|w| = the number of alphabet symbols in the string w
|ε| = 0, |ababb| = 5

Question 6

The set of all strings over Σ

Answer 6

Σ*
contains all strings that can be created by symbols from this alphabet
{a}* = {ε, a, aa, aaa, aaaa,…}

Question 7

w,x ∈ Σ*

wx =

Answer 7

Concatenation of w and x
ORDER MATTERS
w = ab, x = aabb then xw = aabbab and wx = abaabb

Question 8

For all strings w, wε = εw = ?

Answer 8

w, you’re adding nothing

Question 9

w^k

w = string, k = not negative

Answer 9

w^k = concatenation of w, k times
w^0 = ε

Question 10

w^R

Answer 10

reverse of w

(aabbb)^R = bbbaa

Question 11

when is w a substring of x?

Answer 11

when there exists y, z ∈ Σ* (possibly empty) such that x = ywz (y = substring, w = substring, z = substring)

Question 12

when is w a suffix of x?

Answer 12

(second half) if there exists y ∈ Σ* (element of all possible strings) such that x = yw

Question 13

when is w a prefix of x?

Answer 13

(first half) if there exists y ∈ Σ* (element of all possible strings) such that x =wy

Question 14

Language

Answer 14

set of strings made up of symbols from a given alphabet

language OVER Σ = subset of Σ* (alphabet of all possible strings)

Question 15

{a,b}* =

Answer 15

all the possible strings you can create with a and b

{ε, a, b, aa, bb, ba, ab, aab,…}

Question 16

Length of string vs cardinality

Answer 16

{w ∈ {a,b}* | |w| = 8} describing / defining this language as length of string must be 8
vs
|{ε}| = 1 size of the set

Question 17

Operations on Languages (reminder)
L1 - L2 =
L’ =
|L1|

Answer 17

all strings in L1 that are NOT in L2

L' = Σ* - L
|L1| = cardinality

Question 18

Concatenation on Languages
A, C ⊆ Σ*
A = {ab, a} B = {a, ba, aaaa}
𝐴◦𝐵=

Answer 18

A and C are subsets of all possible alphabets
𝐴◦𝐵= {ab, a} {a, ba, aaaa} =
aba, abba, abaaaa, aa, aba, aaaaa
ORDER MATTERS, can’t put symbols of B before A

Question 19

Concatenation on Languages

A^k

Answer 19

concatenation of k A’s = set of strings formed from concatenating elements of A, k times
A^0 = Ø

Question 20

Kleene Star Operation

A* =

Answer 20

A^0 –> A^infinity

ε empty string will always be an element of A*

Question 21

4 Ways to Specify Languages

Answer 21

1. list finite strings
2. Language operations
   L = {aa, ab}* ⋃ {b}
3. Description
   L = {w ∈ {a,b}* |w starts with b}
4. Recursion