CHAPTER 3 Flashcards
(23 cards)
T/F An alphabet Σ is a finite set of symbols
T
………………is a finite sequence of symbols from
a given alphabet (Σ).
A string (or word)
DONE
T/F means joining two strings together in order.
T
T/F If Σ = {a, b, c, . . . , z} and u = ab, v = ra and w = cad,
then
* vu = raab
* uu = abab
* wv = cadra
* uvwuv = abracadabra
T
…………means writing the string in the opposite
order
Example:
* If w = “hello”, then wᴿ = “olleh”.
Reverse of a string
………. For any string w and natural number n, the string
wⁿ means repeating w exactly n times through concatenation
If w = “hi” and n = 3, then w³ = “hihihi”.
Replication
………..The length of a string s, denoted as |s|, is the total
number of symbols (characters) in the string.
Ahmad| = 5 (The string “Ahmad” has 5 letters)
Length
…………………A string with no letters is
⚫ length of empty string is zero:
⚫ Concatenation with an empty string does not change a string:
For any string s, sλ = s and λs = s
Example: “hello” λ = “hello” and λ “world” = “world”.
EMPTY
……….w is any continuous sequence of characters within w
If w = “football”, possible substrings include:
* “foot”
* “ball”
* “ootb”
* “tba”
* “all”
substring
T/F Every string is a substring of itself.
The empty string is a substring of every string.
A substring must preserve the original order of characters. (e.g.,
“otbl” is not a substring of “football”).
T
T/F A string p is a prefix of a string t if t starts with p and may contain extra
characters afterward.
T
T/F Proper Prefix:
A string p is a proper prefix of t if p is a prefix of t but is not equal to t
(i.e., p is shorter than t).
Example:
t = “hello”
* Prefixes: ” “, “h”, “he”, “hel”, “hell”, “hello”
* Proper Prefixes: ” “, “h”, “he”, “hel”, “hell” (excluding “hello” itself)
T
Important prefixes in important notes?
- Every string is a prefix of itself → (e.g., “hello” is a prefix of “hello”).
- The empty string (λ) is a prefix of every string → (e.g., “” is a prefix of “computer”).
T/F A string s is a suffix of a string t if t ends with s and may have additional
characters before it.
T
T/F A string s is a proper suffix of t if s is a suffix of t but is not equal to t (i.e., s is
shorter than t).
T
Important Suffixes in important notes?
- Every string is a suffix of itself.
- The empty string (λ) is a suffix of every string.
………….. Represents the set of all possible strings (including the
empty string) that can be formed from a given alphabet Σ.
The * Operation
……….. is a collection of distinct elements or objects.
set
T/F – A ⊆ B (A is a subset of B)
– A ⊂ B (A is a proper subset of B)
T
T/F ⚫ Set Membership (∈):
* If a∈A it means a is an element of set A
⚫ Cardinality of a Set (|A|):
* The number of elements in a set.
* Example: For A= {1,2,3} the cardinality is ∣A∣=3.
⚫ Complement of a Set (A’):
* The set of all elements not in set A
* Example: If U={1,2,3,4} and A={1,2}, then A′={3,4}
T
……………. It is a subset of Σ*, meaning it consists of some (or all) possible strings over Σ.
language
