CHAPTER 2 - Formal Languages, Alphabets, String, and Notation

Alphabet

It is defined as a finite set of symbols.

Alphabet

any nonempty finite set.

Symbols

The members of the alphabet are the _______ of the alphabet. Denoted by ⅀

String

A "______" over an alphabet is a finite sequence of symbols from that alphabet, which is usually written next to one another and not separated by commas

Length

The "______" of a string is its length as a sequence. The length of a string w is written as |w|

Reverse string

"tite" -> "etit"

Substring

z is a _________ of w if z appears consecutively within w. • Example: If ∑a = {a, b, ..., z) then "deck" is a substring of "abcdeckabcjkl"

Concatenation

the string obtained by appending y to the end of x, as in x1x2...xm y1 y2... yn

Suffix

last letter of the string

Prefix

first letter of the string