PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: Very high
[parent] word (Definition)

Given a set $ \Sigma$, a 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 empty word, typically denoted by $ \lambda$. The set of words over $ \Sigma$ is denoted $ \Sigma^*$.

Examples.

  1. 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$.
  2. 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$.
  3. 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\vert\quad\rangle$ a word could be the commutator $ [a,b]=aba^{-1}b^{-1}$.

Remarks

  • 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.
  • A word $ u$ is called a 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$ occurs in $ v$, or that $ v$ contains $ u$. For example, “math” is a subword of “mathematics”. Given the equation $ v=xuy$, we call the triple $ (x,u,y)$ an occurrence of $ u$ in $ v$. The collection of occurrences of $ u$ in $ v$ is denoted $ O(u,v)$. The number of occurrences of $ u$ in $ v$ defined as the cardinality of $ O(u,v)$, and written $ \vert u\vert _v$. For example, the number of occurrences of subword $ a^3$ in $ a^3ba^5c$ is $ 4$, since
    $\displaystyle 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.$

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:

  1. if $ a,b$ do not contain either $ +$ or $ =$, then $ ab$ is a sensible word;
  2. if a two sensible words $ a,b$ do not contain the symbol $ =$, then $ a+b$ and $ a=b$ are sensible words;
  3. 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
  • $ a$
  • $ a_1+a_2+\cdots +a_n$
  • $ a_1+a_2+\cdots + a_n = b_1+b_2+\cdots + b_m$.
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 language. The collection of all sensible words described above is called the language generated by $ 0,\ldots,9$ under the rules above. In logic, one calls these sensible words well-formed formulas, or formulas or wff for short.



"word" is owned by juanman. [ full author list (2) ]
(view preamble)

View style:

See Also: group, straight-line program, alphabet, language, concatenation, alternative treatment of concatenation

Other names:  well-formed formula, wff
Also defines:  empty word, well formed formula, subword, occur in, occurrence
Keywords:  generator, presentation

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: formulas, logic, language, right, grammar, cardinality, collection, equation, integers, commutator, free group, theory, group, contains, alphabet, binary operation, associative, finite, juxtaposition, string
There are 108 references to this entry.

This is version 23 of word, born on 2006-07-12, modified 2007-11-11.
Object id is 8137, canonical name is Word.
Accessed 3018 times total.

Classification:
AMS MSC: 20-00 (Group theory and generalizations :: General reference works )
 20A05 (Group theory and generalizations :: Foundations :: Axiomatics and elementary properties)
 08A99 (General algebraic systems :: Algebraic structures :: Miscellaneous)
 03D40 (Mathematical logic and foundations :: Computability and recursion theory :: Word problems, etc.)
 03B99 (Mathematical logic and foundations :: General logic :: Miscellaneous)
 03B65 (Mathematical logic and foundations :: General logic :: Logic of natural languages)
 03B05 (Mathematical logic and foundations :: General logic :: Classical propositional logic)
 03B10 (Mathematical logic and foundations :: General logic :: Classical first-order logic)
Pending Errata and Addenda
None.
[ View all 9 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)