wordWord2006-07-12 08:19:582009-09-04 19:23:31Definitiongroupempty wordwell formed formulasubwordoccur inoccurrence$\omega$-wordgeneratorpresentation% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\PMlinkescapeword{generated by}
Given a set $\Sigma$, a \emph{word} (or a string) over $\Sigma$ is a juxtaposition (variously called concatenation or multiplication) of a finite number of elements in $\Sigma$. The juxtaposition is taken as an associative binary operation on $\Sigma$. A word with zero number of elements is called an \emph{empty word}, typically denoted by $\lambda$ or $\epsilon$. The set of words over $\Sigma$ is denoted $\Sigma^*$.
\textbf{Examples}.
\begin{enumerate}
\item
If $\Sigma = \lbrace a,b,c,\ldots, x,y,z\rbrace$, the English alphabet written in the lower case, then ``good'', ``mathematics'', ``fasluiwh'' are all words (without the double quotes) over $\Sigma$, where as ``PlanetMath'' is not, because it contains upper case letters, which are not in $\Sigma$.
\item
Let $\Sigma=\lbrace 0,1,2,3,4,5,6,7,8,9,+,=\rbrace$. Then ``$12$'', ``$0345$'', ``$9+3$'', ``$87=123$'', ``$++231++$'', ``$6+7=13$'', ``$7=$'' are also words over $\Sigma$.
\item
The notion of words is used extensively in group theory. The juxtaposition here is the group multiplication, as the multiplication is associative. In other words, if $g_1,g_2,...,g_m$ are elements in $G$ then we can form the word $w=g_1g_2\cdots g_m\in G$. For example, in the free group $\langle a,b|\quad\rangle$ a word could be the commutator $[a,b]=aba^{-1}b^{-1}$.
\end{enumerate}
\textbf{Remarks}
\begin{itemize}
\item
$\Sigma^*$ is a monoid with juxtaposition as the monoid multiplication, and $\lambda$, the empty word, as the multiplicative identity.
\item
For any element $a$ in $\Sigma$, define $a^0=\lambda$, and $a^{n+1}=a^na$ for non-negative integers $n$. Then $a^{n+m}=a^na^m$ since juxtaposition is associative.
\item
A word $u$ is called a \emph{subword} of $v$ if $v=xuy$, for some words $x$ and $y$ (may be empty words). If $u$ is a subword of $v$, we also say that $u$ \emph{occurs in} $v$, or that $v$ \emph{contains} $u$. For example, ``math'' is a subword of ``mathematics''. Given the equation $v=xuy$, we call the triple $(x,u,y)$ an \emph{occurrence} of $u$ in $v$. The collection of occurrences of $u$ in $v$ is denoted $O(u,v)$. The \emph{number of occurrences} of $u$ in $v$ defined as the cardinality of $O(u,v)$, and written $|u|_v$. For example, the number of occurrences of subword $a^3$ in $a^3ba^5c$ is $4$, since $$O(a^3,a^3ba^5c)=\lbrace (\lambda,a^3,ba^5c),(a^3b,a^3,a^2c), (a^3ba, a^3, ac), (a^3ba^2,a^3,c)\rbrace.$$
\item
Words, by definition, are finite in length. This notion can be generalized: an \emph{infinite word}, or more precisely, a \emph{$\omega$-word}, over an alphabet $\Sigma$ is just a function from $\mathbb{N}$ to $\Sigma$. The set of all words over $\Sigma$, finite or infinite, is $\Sigma^* \cup \Sigma^{\mathbb{N}}$, and is denoted by $\Sigma^{\infty}$ or $\Sigma^{\omega}$.
\end{itemize}
\subsubsection*{Generating Words using Rules}
Some of the words in the second example above, such as ``$++231++$'' and ``$7=$'', 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 $\Sigma$ 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 $0,1,\ldots,9$ are sensible words. To form new sensible words, we have the rules:
\begin{enumerate}
\item
if $a,b$ do not contain either $+$ or $=$, then $ab$ is a sensible word;
\item
if a two sensible words $a,b$ do not contain the symbol $=$, then $a+b$ and $a=b$ are sensible words;
\item
the only sensible words are the initially declared sensible words and those that can be formed by the previous two rules.
\end{enumerate}
It is not hard to see based on the initially declared sensible words and the rules has one of the forms
\begin{itemize}
\item $a$
\item $a_1+a_2+\cdots +a_n$
\item $a_1+a_2+\cdots + a_n = b_1+b_2+\cdots + b_m$.
\end{itemize}
where $a,a_i,b_j$ are words without any occurrence of $+$ and $=$, over $\Sigma$. 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 \emph{language}. The collection of all sensible words described above is called \emph{the language generated by} $0,\ldots,9$ under the rules above. In logic, one calls these sensible words \emph{well-formed formulas}, or \emph{formulas} or \emph{wff} for short.