Week 1 - Strings and Languages Flashcards
What is the definition of ‘alphabet’ in computing?
A finite and non-empty set of symbols.
What is a member of an ‘alphabet’ called?
A symbol.
In computing, is ‘alphabet’ just the normal alphabet?
No, it can be any set of symbols.
Examples:
{0, 1}
{a, b, c, ..., x, y, z}
{0, 1, a, b, +, =, @, #}What is a string/word?
A sequence of symbols from a given ‘alphabet’.
What is an empty string?
A string containing no symbols. This can be formed from any ‘alphabet’.
What is another name from the empty string? Another way to represent it?
ε (Aka: Epsilon).
How do we normally denote the length of word w for example?
|w|
some examples
|waterhorn| = 9
|dice| = 4
How do we normally denote the reverse word of word w?
w^R
e.g.
dice^R = ecid
abc^R = cba
What is a substring?
A sequence of symbols that can be directly found as part of a string/word in the exact order specicified in the substring.
e.g.
water and horn are substrings of waterhorn.
a, b, c, ab and bc are all substrings of abc.
What is a prefix?
It is a substring that is found on the leftmost side of a word.
e.g.
‘water’, ‘wa’ and ‘waterho’ are prefixes of ‘waterhorn’.
‘a’, ‘ab’ and ‘abc’ are prefixes of ‘abc’.
TRUE OR FALSE: Can ε count as a prefix/suffix for a word.
TRUE, because all words can technically start with nothing.
TRUE OR FALSE: A word can count as a prefix/suffix for itself.
TRUE, because a substring is just any ordered seqeunce found within a word.
What is a suffix?
It is a substring that is found on the rightmost side of a word.
e.g.
‘horn’, ‘rn’ and ‘aterhorn’ are suffixes of ‘waterhorn’.
‘c’, ‘bc’ and ‘abc’ are suffixes of ‘abc’.
What is concatentation?
Appending together words/strings, so that at the end of a word another word starts. e.g. w = waterhorn and z = abc wz = waterhornabc zw = abcwaterhorn zwz = abcwaterhornzbc wwww = waterhornwaterhornwaterhornwaterhorn etc.. z^2 = zz = abcabc
TRUE OR FALSE: If z is a prefix of word w, then there must exist a string u in the same alphabet such that w = zu.
TRUE.
