Can a formal language contain infinitely many strings?

Yes. Each individual string is finite, but the set can have infinitely many members.

Is every formal language regular?

No. Regular languages are one restricted class within the broader concept.

Does a syntactically valid program necessarily do what its author intended?

No. Structural validity does not establish correct meaning or behavior.

AI Glossary / Natural language and speech / Intermediate

Formal language

Definition

A formal language is a set of finite strings built from a specified alphabet of symbols. The set determines which strings belong to the language. Grammars, regular expressions, and computational models can describe particular classes of formal languages, making the concept central to parsing, programming languages, and theoretical computer science.

What it means

Here, “language” does not necessarily mean a human language such as English. It can mean all binary strings ending in 01, all correctly structured commands in a small notation, or the strings generated by a grammar.
“Formal” also does not mean polite or businesslike wording. It means that the objects and membership conditions are treated mathematically.
The alphabet provides the available symbols; a string is an ordered sequence of those symbols; and a language is a set containing selected strings. Keeping these three levels separate is essential. The same alphabet can support many different languages, because different membership conditions select different strings.

How it works

Let Σ denote an alphabet, conventionally a finite nonempty set in introductory automata theory. The notation Σ* denotes all finite strings over that alphabet, including the empty string ε.
A formal language L over Σ is any subset of Σ*. A grammar can specify how to generate members, while an appropriate recognizer can test membership for languages it is capable of recognizing.
Different representation systems have different expressive power. Regular languages can be recognized by finite automata; other language classes require more powerful formalisms. The general definition of a formal language does not promise that every language has a practical membership algorithm.
Syntax and meaning are also separate. A string can satisfy a formal structural rule without expressing a sensible or permitted action in an application.

Three practical examples

A compiler checks whether a sequence of tokens follows the grammar of a programming language.
An input validator recognizes identifiers that obey a precisely specified pattern.
A natural-language parsing exercise uses a small grammar to define which simplified sentences it can derive, while recognizing that the grammar models only a limited fragment of real usage.

Think of it this way

Think of a club whose members are strings rather than people. The alphabet supplies the pieces from which applicants are made, and the membership condition decides which strings belong. The analogy is limited because formal languages can be infinite and mathematically defined even when no usable membership-checking procedure exists.

Worked example

Choose the alphabet Σ = {a, b}. Define L as all strings over this alphabet that contain exactly two occurrences of b.
The string “bba” belongs to L because it contains two b symbols. So does “ababa.” The string “aaa” does not belong because it contains none, and “bbb” does not belong because it contains three.
The empty string ε belongs to Σ* but not to L. This distinguishes all possible strings over the alphabet from the particular language selected by the rule.
A finite-state recognizer can track four situations: zero b symbols seen, one seen, exactly two seen, and more than two seen. Reading a leaves the count category unchanged. Reading b advances it, with the “more than two” situation remaining rejecting.
The recognizer accepts only if the input ends in the “exactly two” state. For “ababa,” its b-count categories progress 0, 0, 1, 1, 2, 2, so it accepts. This is a checked teaching construction, not a claim that all formal languages can be recognized with four states.

Illustrative case study

In a fictional project, Oak Forms accepts reference codes consisting of two uppercase letters followed by three digits. The team documents this syntax and tests valid codes alongside strings with missing digits, extra characters, or lowercase letters.
It then performs a separate lookup to determine whether an accepted code identifies an existing record. A string can satisfy the pattern while naming nothing in the database.
The imagined case shows how formal syntax supports reliable validation without replacing semantic checks. It does not treat a regular expression as a complete authorization or business-rule system.

Common misconceptions and mistakes

An alphabet is not a language. It is a set of symbols, while a language is a set of strings made from symbols.
The empty string is not the empty language. The former is one string of length zero; the latter contains no strings at all.
A grammar is not identical to the language it generates. Different grammars can generate the same set of strings, potentially with different structures.
Finally, a formal grammar for an English fragment is not a complete account of human language. Its precise acceptance boundary reflects the model rather than every nuance of natural usage.

Business use

Formal-language concepts help teams specify inputs, exchange formats, commands, and parser behavior clearly. A precise structural definition makes both accepted and rejected examples easier to test.
For AI systems that produce structured output, formal constraints can help check whether the output fits a required syntax. That check does not establish factual correctness, suitability, or whether an operation should be performed.
Good specifications distinguish tokenization, syntax, and later meaning or business-rule checks. They also define boundary cases such as empty input, spaces, character sets, and whether the whole input must match rather than merely contain a matching fragment.

Check your understanding

Over Σ = {0, 1}, let L contain strings with exactly one 1. Do “00100,” “101,” and ε belong?

Answer: “00100” belongs because it has one 1. “101” has two and does not belong. The empty string has none and also does not belong.

Related terms

Context-free grammar
Parsing
Syntax
Semantics
Alphabet
string
empty string
formal grammar
regular language
finite automaton
language recognition

Learn next

Begin with sets and finite strings, then work through a small finite automaton by hand. Next, study regular expressions and context-free grammars to see different ways of specifying languages. Keep asking separately whether a string has valid structure and whether it has the intended meaning.

Sources

Stanford CS103, original course slides on alphabets, strings, languages, and finite automata: https://web.stanford.edu/class/archive/cs/cs103/cs103.1264/lectures/14/Condensed%20Lecture%20Slides.pdf. Jurafsky and Martin, Speech and Language Processing, context-free grammars and the formal languages they define: https://web.stanford.edu/~jurafsky/slp3/19.pdf. Independent review checked the CS103 alphabet, finite-string, language-subset and automaton-acceptance definitions.

Previous: Formal concept analysis Next: Formal logic