Given a set , a word (or a string) over is a juxtaposition (variously called concatenation or multiplication) of a finite number of elements in . The juxtaposition is taken as an associative binary operation on . A word with zero number of elements is called an empty word, typically denoted by or . The set of words over is denoted .
If , the English alphabet written in the lower case, then “good”, “mathematics”, “fasluiwh” are all words (without the double quotes) over , where as “PlanetMath” is not, because it contains upper case letters, which are not in .
Let . Then “”, “”, “”, “”, “”, “”, “” are also words over .
A word is called a subword of if , for some words and (may be empty words). If is a subword of , we also say that occurs in , or that contains . For example, “math” is a subword of “mathematics”.
Given the equation , we call the triple an occurrence of in . The collection of occurrences of in is denoted . The number of occurrences of in defined as the cardinality of , and written . The position of occurrence of in is the length of plus .
For example, the number of occurrences of subword in is , since
The positions of these occurrences are , and , respectively.
Generating Words using Rules
Some of the words in the second example above, such as “” and “”, do not make any mathematical sense. The way to define words that make sense is through a process called definition by recursion. First, we declare that certain words over are sensible. Then, we have a set of rules or a grammar that dictates how new sensible words can be formed from the old ones. Any word that can be formed from the old words by these rules in a finite number of steps is called sensible.
In the last example, we could declare that all symbols are sensible words. To form new sensible words, we have the rules:
if do not contain either or , then is a sensible word;
if a two sensible words do not contain the symbol , then and are sensible words;
the only sensible words are the initially declared sensible words and those that can be formed by the previous two rules.
It is not hard to see based on the initially declared sensible words and the rules has one of the forms
where are words without any occurrence of and , over . As a result, we see that all words in the previous example are sensible (whether they are right or wrong), except “++231++” and “7=”, since they are not in any one of the forms specified above. Note that the third rule above ensures that “++231++” and “7=” are not sensible. Without it, we would be unable to say for sure if these words are sensible or not.
Generally, any collection of words is called a language. The collection of all sensible words described above is called the language generated by under the rules above. In logic, one calls these sensible words well-formed formulas, or formulas or wff for short.
|Date of creation||2013-03-22 16:04:44|
|Last modified on||2013-03-22 16:04:44|
|Last modified by||juanman (12619)|
|Defines||well formed formula|