Alphabet (formal languages)

Base set of symbols with which a language is formed

Part of a series on

Formal languages

Key concepts

* Formal system
* Alphabet
* Syntax
* Formal semantics
* Semantics (programming languages)
* Formal grammar
* Formation rule
* Well-formed formula
* Automata theory
* Regular expression
* Production
* Ground expression
* Atomic formula

Applications

* Formal methods
* Propositional calculus
* Predicate logic
* Mathematical notation
* Natural language processing
* Programming language theory
* Mathematical linguistics
* Computational linguistics
* Syntax analysis
* Formal verification
* Automated theorem proving

* v
* t
* e

In formal language theory, an alphabet, sometimes called a vocabulary (see Nonterminal Symbols), is a non-empty set of indivisible symbols/characters/glyphs,[1] typically thought of as representing letters, characters, digits, phonemes, or even words.[2][3] The definition is used in a diverse range of fields including logic, mathematics, computer science, and linguistics. An alphabet may have any cardinality ("size") and, depending on its purpose, may be finite (e.g., the alphabet of letters "a" through "z"), countable (e.g.,  { v 1 , v 2 , … } {\displaystyle \\{v_{1},v_{2},\ldots \\}} ), or even uncountable (e.g.,  { v x : x ∈ R } {\displaystyle \\{v_{x}:x\in \mathbb {R} \\}} ).

Strings, also known as "words" or "sentences", over an alphabet are defined as a sequence of the symbols from the alphabet set.[4] For example, the alphabet of lowercase letters "a" through "z" can be used to form English words like "iceberg" while the alphabet of both upper and lower case letters can also be used to form proper names like "Wikipedia". A common alphabet is {0,1}, the binary alphabet, and "00101111" is an example of a binary string. Infinite sequences of symbols may be considered as well (see Omega language).

Strings are often written as the concatenation of their symbols, and when using this notational convention it is convenient for practical purposes to restrict the symbols in an alphabet so that this notation is unambiguous. For instance, if the two-member alphabet is {00,0}, a string written in concatenated form as "000" is ambiguous because it is unclear if it is a sequence of three "0" symbols, a "00" followed by a "0", or a "0" followed by a "00". However, this is a limitation on the notation for writing strings, not on their underlying definitions. Like any finite set, {00,0} can be used as an alphabet, whose strings can be written unambiguously in a different notational convention with commas separating their elements: 0,00 ≠ 0,0,0 ≠ 00,0.

## Notation

[edit]

By definition, the alphabet of a formal language  L {\displaystyle L} over  Σ {\displaystyle \Sigma } is the set  Σ {\displaystyle \Sigma } , which can be any non-empty set of symbols from which every string in  L {\displaystyle L} is built. For example, the set  Σ = { _ , a , … , z , A , … , Z , 0 , 1 , … , 9 } {\displaystyle \Sigma =\\{\\_,\mathrm {a} ,\dots ,\mathrm {z} ,\mathrm {A} ,\dots ,\mathrm {Z} ,0,\mathrm {1} ,\dots ,\mathrm {9} \\}} can be the alphabet of the formal language  L {\displaystyle L} that means "all variable identifiers in the C programming language". It is not required to use every symbol in the alphabet of  L {\displaystyle L} for its strings.

Given an alphabet  Σ {\displaystyle \Sigma } , the set of all strings of length  n {\displaystyle n} over the alphabet  Σ {\displaystyle \Sigma } is indicated by  Σ n {\displaystyle \Sigma ^{n}} . The set  ⋃ i ∈ N Σ i {\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}} of all finite strings (regardless of their length) is indicated by the Kleene star operator as  Σ ∗ {\displaystyle \Sigma ^{*}} , and is also called the Kleene closure of  Σ {\displaystyle \Sigma } . The notation  Σ ω {\displaystyle \Sigma ^{\omega }} indicates the set of all infinite sequences over the alphabet  Σ {\displaystyle \Sigma } , and  Σ ∞ {\displaystyle \Sigma ^{\infty }} indicates the set  Σ ∗ ∪ Σ ω {\displaystyle \Sigma ^{\ast }\cup \Sigma ^{\omega }} of all finite or infinite sequences.

For example, using the binary alphabet {0,1}, the strings ε, 0, 1, 00, 01, 10, 11, 000, etc. are all in the Kleene closure of the alphabet (where ε represents the empty string).

## Applications

[edit]

Alphabets are important in the use of formal languages, automata and semiautomata. In most cases, for defining instances of automata, such as deterministic finite automata (DFAs), it is required to specify an alphabet from which the input strings for the automaton are built. In these applications, an alphabet is usually required to be a finite set, but is not otherwise restricted.

When using automata, regular expressions, or formal grammars as part of string-processing algorithms, the alphabet may be assumed to be the character set of the text to be processed by these algorithms, or a subset of allowable characters from the character set.

## See also

[edit]

* Combinatorics on words
* Terminal and nonterminal symbols

## References

[edit]

1. ^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics. PWS-Kent. p. 114\. ISBN 0-53492-373-9. "An alphabet is a nonempty finite set the members of which are called symbols or characters."
2. ^ Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Mathematical Logic (2nd ed.). New York: Springer. p. 11\. ISBN 0-387-94258-0. "By an alphabet A {\displaystyle {\mathcal {A}}} we mean a nonempty set of symbols."
3. ^ Rosen, Kenneth H. (2012). Discrete Mathematics and Its Applications (PDF) (7th ed.). New York: McGraw Hill. pp. 847–851\. ISBN 978-0-07-338309-5. "A vocabulary (or alphabet) V is a finite, nonempty set of elements called symbols. A word (or sentence) over V is a string of finite length of elements of V."
4. ^ Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (PDF) (Third ed.). Springer. p. xx. ISBN 978-1-4419-1220-6. "If 𝗔 is an alphabet, i.e., if the elements 𝐬 ∈ 𝗔 are symbols or at least named symbols, then the sequence (𝐬1,...,𝐬n)∈𝗔n is written as 𝐬1···𝐬n and called a string or a word over 𝗔."

## Literature

[edit]

* John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X.

* v
* t
* e

Mathematical logic

General|

* Axiom
* list
* Cardinality
* First-order logic
* Formal proof
* Formal semantics
* Foundations of mathematics
* Information theory
* Lemma
* Logical consequence
* Model
* Theorem
* Theory
* Type theory

Theorems (list)
and paradoxes|

* Gödel's completeness and incompleteness theorems
* Tarski's undefinability
* Banach–Tarski paradox
* Cantor's theorem, paradox and diagonal argument
* Compactness
* Halting problem
* Lindström's
* Löwenheim–Skolem
* Russell's paradox

Logics|

| Traditional|

* Classical logic
* Logical truth
* Tautology
* Proposition
* Inference
* Logical equivalence
* Consistency
* Equiconsistency
* Argument
* Soundness
* Validity
* Syllogism
* Square of opposition
* Venn diagram

|

Propositional|

* Boolean algebra
* Boolean functions
* Logical connectives
* Propositional calculus
* Propositional formula
* Truth tables
* Many-valued logic
* 3
* finite
* ∞

Predicate|

* First-order
* list
* Second-order
* Monadic
* Higher-order
* Fixed-point
* Free
* Quantifiers
* Predicate
* Monadic predicate calculus

Set theory|

* Set
* hereditary
* Class
* (Ur-)Element
* Ordinal number
* Extensionality
* Forcing
* Relation
* equivalence
* partition
* Set operations:
* intersection
* union
* complement
* Cartesian product
* power set
* identities

Types of sets|

* Countable
* Uncountable
* Empty
* Inhabited
* Singleton
* Finite
* Infinite
* Transitive
* Ultrafilter
* Recursive
* Fuzzy
* Universal
* Universe
* constructible
* Grothendieck
* Von Neumann

Maps and cardinality|

* Function/Map
* domain
* codomain
* image
* In/Sur/Bi-jection
* Schröder–Bernstein theorem
* Isomorphism
* Gödel numbering
* Enumeration
* Large cardinal
* inaccessible
* Aleph number
* Operation
* binary

Set theories|

* Zermelo–Fraenkel
* axiom of choice
* continuum hypothesis
* General
* Kripke–Platek
* Morse–Kelley
* Naive
* New Foundations
* Tarski–Grothendieck
* Von Neumann–Bernays–Gödel
* Ackermann
* Constructive

Formal systems (list),
language and syntax|

* Alphabet
* Arity
* Automata
* Axiom schema
* Expression
* ground
* Extension
* by definition
* conservative
* Relation
* Formation rule
* Grammar
* Formula
* atomic
* closed
* ground
* open
* Free/bound variable
* Language
* Metalanguage
* Logical connective
* ¬
* ∨
* ∧
* →
* ↔
* =
* Predicate
* functional
* variable
* propositional variable
* Proof
* Quantifier
* ∃
* !
* ∀
* rank
* Sentence
* atomic
* spectrum
* Signature
* String
* Substitution
* Symbol
* function
* logical/constant
* non-logical
* variable
* Term
* Theory
* list

Example axiomatic
systems (list)|

* of arithmetic:
* Peano
* second-order
* elementary function
* primitive recursive
* Robinson
* Skolem
* of the real numbers
* Tarski's axiomatization
* of Boolean algebras
* canonical
* minimal axioms
* of geometry:
* Euclidean:
* Elements
* Hilbert's
* Tarski's
* non-Euclidean

* Principia Mathematica

Proof theory|

* Formal proof
* Natural deduction
* Logical consequence
* Rule of inference
* Sequent calculus
* Theorem
* Systems
* axiomatic
* deductive
* Hilbert
* list
* Complete theory
* Independence (from ZFC)
* Proof of impossibility
* Ordinal analysis
* Reverse mathematics
* Self-verifying theories

Model theory|

* Interpretation
* function
* of models
* Model
* equivalence
* finite
* saturated
* spectrum
* submodel
* Non-standard model
* of arithmetic
* Diagram
* elementary
* Categorical theory
* Model complete theory
* Satisfiability
* Semantics of logic
* Strength
* Theories of truth
* semantic
* Tarski's
* Kripke's
* T-schema
* Transfer principle
* Truth predicate
* Truth value
* Type
* Ultraproduct
* Validity

Computability theory|

* Church encoding
* Church–Turing thesis
* Computably enumerable
* Computable function
* Computable set
* Decision problem
* decidable
* undecidable
* P
* NP
* P versus NP problem
* Kolmogorov complexity
* Lambda calculus
* Primitive recursive function
* Recursion
* Recursive set
* Turing machine
* Type theory

Related|

* Abstract logic
* Algebraic logic
* Automated theorem proving
* Category theory
* Concrete/Abstract category
* Category of sets
* History of logic
* History of mathematical logic
* timeline
* Logicism
* Mathematical object
* Philosophy of mathematics
* Supertask

Mathematics portal
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template