Please enable JavaScript.
Coggle requires JavaScript to display documents.
String Algorithms (alphabet A (string on alphabet A (string x is a factor…
String Algorithms
alphabet A
string on alphabet A
-
-
a product (or concatenation) of two strings x and y is a string z that starts with letters from x and ends with letters from y
-
-
A set of all strings of an A
without the empty string is denoted by A+ #
-
-
-
An alphabet A is a nonempty finite set of elements called letters. A string on an alphabet A is a finite sequence of elements of A. A zero letter sequence is called empty string
Regular expressionThe regular expressions on an alphabet A and the languages they describe, the regular languages, are recursively defined as follows:
- 0 and 1 are regular expressions that recursively describe O(empty set) and {e}
- for every letter a from A, a is a regular expression that describes singleton {a}
- if x and y are regular expressions respectively describing regular languages X and Y, then (x) + (y), (x) * (y), and (x)* are regular expressions that respectively describe the regular languages X + Y, X Y, X
-
Automaton M on the alphabet A is composed of a finite set Q of states, of an initial state q, of a set T from Q of terminal states, and a set of F from QxAxQ of transitions
suffix function sigma is A* -> {0..m} such that sigma(x) = max { k: P -| x }
sigma(x) is the length of the longest prefix of P that is also a suffix of x
P = ab
s(ccaca) = 1; s(ccab) = 2
final state function phi(x) denotes the state that M ends up in, after scanning the string x