ONT Formal Languages
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
It is time to introduce a few elements of formal language theory
that will be found to have a general utility. The initial parts
of this presentation are fairly standard material, though I will
be trying out several innovations later on, as we get under way.
| Note On Notation. In transcribing this text from my archives,
| I will be using a few antic devices and display conventions
| from the Asciimolean Museum of semi-antique languages.
|
| @A@ = attic A = greek alpha,
| #A# = bold A,
| $A$ = curly A = script A,
| !A! = singly underscored A,
| %A% = doubly underscored A,
| x^j = x superscript j,
| x_j = x subscript j.
¤~~~~~~~~~¤~~~~~~~~~¤~DISSERTATION~¤~~~~~~~~~¤~~~~~~~~~¤
| Document History:
|
| Subject: Inquiry Driven Systems: An Inquiry Into Inquiry
| Contact: Jon Awbrey <jawbrey@oakland.edu>
| Version: Draft 8.62
| Created: 23-Jun-1996
| Revised: 02-Oct-2001
| Advisor: M.A. Zohdy
| Setting: Oakland University, Rochester, Michigan, USA
| Excerpt: Subsection 1.3.10.9 (The Cactus Language: Syntax)
A few definitions from formal language theory are required at this point.
An "alphabet" is a finite set of signs, typically, !A! = {a_1, ..., a_n}.
A "string" over an alphabet !A! is a finite sequence of signs from !A!.
The "length" of a string is just its length as a sequence of signs.
A sequence of length 0 yields the "empty string", here presented as "".
A sequence of length k > 0 is typically presented in the concatenated forms:
s_1 s_2 ... s_(k-1) s_k,
or
s_1 . s_2 . ... . s_(k-1) . s_k,
with s_j in !A!, for all j = 1 to k.
Two alternative notations are often useful:
1. !e! = @e@ = "" = the empty string.
2. %e% = {!e!} = {""} = the language consisting of a single empty string.
The "kleene star" !A!* of alphabet !A! is the set of all strings over !A!.
In particular, !A!* includes among its elements the empty string !e!.
The "surplus" !A!^+ of an alphabet !A! is the set of all positive length
strings over !A!, in other words, everything in !A!* but the empty string.
A "formal language" !L! over an alphabet !A! is a subset !L! c !A!*.
If S is a string over !A! and if S is an element of !L!, then it is
customary to call S a "sentence" of !L!. Thus, a formal language !L!
is defined by specifying its elements, which amounts to saying what it
means to be a sentence of !L!.
One last device turns out to be useful in this connection.
If S is a string that ends with a sign t, then S . t^-1 is
the string that results by deleting the terminal t from S.
In this context, I make the following distinction:
1. By "deleting" an appearance of a sign,
I mean replacing it with an appearance
of the empty string "".
2. By "erasing" an appearance of a sign,
I mean replacing it with an appearance
of the blank symbol " ".
A "token" is a particular appearance of a sign.
¤~~~~~~~~~¤~~~~~~~~~¤~NOITATRESSID~¤~~~~~~~~~¤~~~~~~~~~¤