Theory of Computation

Context-free grammar language generation

A context-free grammar (CFG) generates strings by replacing one non-terminal at a time until only terminal symbols remain. The language L(G) is the set of terminal strings that can be derived from the start symbol, and every intermediate string is a sentential form. To find L(G), first determine what each non-terminal generates on its own, then combine these sets through the rules, because a rule A \to \alpha B \beta places everything that B generates inside A.

A self-embedding rule forces the outer symbols to be matched in pairs. The grammar S \to aSb \mid c generates \{a^n c b^n \mid n \ge 0\}, since each application of S \to aSb adds one a on the left and one b on the right. A recursive non-terminal does not by itself make a language non-regular. The rules Y \to cY \mid Yd \mid c \mid d generate c^i x d^j with one middle symbol x \in \{c, d\}, so the language is c^*(c+d)d^*, which is regular. To check such a description, show both inclusions: every derived string has the stated form, and every string of that form can be derived.

A non-terminal with rules B \to b \mid bB derives exactly the nonempty strings of b's, so a rule S \to aaB yields a^2 b^+. Fixed prefixes and suffixes can be read directly from the grammar in this way.

For a grammar whose rules change the number of pending non-terminals, a counting invariant often gives the answer quickly. In S \to aSbS \mid c, each use of aSbS adds one extra S and one b, and each c removes one S. Since a derivation must end with no S left, the number of c's equals the number of b's plus one. Adding the rule S \to aS does not change the number of S symbols, so the same invariant still holds. Bounds of this kind are usually proved for each non-terminal by induction on the length of a derivation, and the bound for the start symbol follows by summing the bounds of its parts.

FIRST and FOLLOW sets test whether a grammar can be parsed deterministically. \mathrm{FIRST}(\alpha) is the set of terminals that can begin a string derived from \alpha, together with \epsilon if \alpha can derive the empty string. \mathrm{FOLLOW}(A) is the set of terminals that can appear immediately to the right of A in some sentential form. If a production A \to \alpha B ends with B, then \mathrm{FOLLOW}(A) is included in \mathrm{FOLLOW}(B), and the same inclusion holds for A \to \alpha B \beta when \beta can derive \epsilon. Thus placing a terminal after R, as in S \to Rf, makes \mathrm{FOLLOW}(R) equal to that terminal, whereas S \to fR would copy \mathrm{FOLLOW}(S) into \mathrm{FOLLOW}(R).

A grammar is ambiguous when some string has two different parse trees, equivalently two distinct leftmost derivations. The grammar S \to aSbS \mid bS \mid \epsilon is ambiguous, because the string abb has two parse trees, one in which the first S becomes \epsilon and the second becomes bS, and one in the reverse assignment. Ambiguity is a property of the grammar, while membership in any CFL is decidable, for example by the CYK algorithm.

An LL(1) parser chooses a production from one lookahead symbol, so it fails when two alternatives of the same non-terminal share a FIRST symbol. The dangling-else rules S \to \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S \mid a are not LL(1) because both alternatives begin with the same prefix, and they are ambiguous because an else can attach to either if.

Closure properties of context-free languages

Context-free languages (CFLs) are closed under union, concatenation and Kleene star, which follow directly from combining grammars with a new start symbol. They are also closed under intersection with a regular language, because the product of a pushdown automaton and a finite automaton is again a pushdown automaton. They are not closed under complement, and therefore not under intersection or difference in general. When a regular language L_1 is combined with a CFL L_2, the difference L_1 - L_2 = L_1 \cap \overline{L_2} need not be context-free, because \overline{L_2} may fail to be context-free for a suitable CFL L_2.

Expressions built from a regular set and a CFL can often be simplified with set identities before closure is checked. For example, L_2 \cap (L_1 \cup \overline{L_1}) = L_2, because L_1 \cup \overline{L_1} = \Sigma^*. A regular set combined through complements and unions can therefore collapse to a CFL or a regular set, and both are context-free.

Reversal and concatenation are common operations in these questions. The set of even palindromes \{ww^R\} is a CFL, and the concatenation of two CFLs such as \{ww^R\} and \{xx^R\} is again a CFL. However, when the two parts are interleaved, as in \{wxw^Rx^R\}, the pattern creates a crossing dependency that a pushdown automaton cannot track, and a pumping argument on a suitably chosen string shows that the language is not context-free. A parameter that is allowed to be zero may also make a language collapse. If n can be 0 in \{a^n w a^n\}, then every string w is included, so the language is all of \{a,b\}^*, which is regular and therefore context-free.

Closure properties are often matched across language classes. Recursive languages are closed under union and intersection, regular languages are closed under union, intersection and complement, and context-free languages are not closed under complement.

Regular expression from finite automaton

A regular expression for a finite automaton is found by collecting the paths from the start state to an accepting state, where each loop may be repeated any number of times. A loop at a state with label r contributes r^*, a cycle through two or more states contributes the star of its concatenated label, and parallel paths are combined with +. The typical answer therefore has the shape (\text{cycles at the start})^*(\text{paths to accepting states}). For example, a DFA that reads a 1 and then accepts on any number of 0s has the expression 10^*, because the self-loop on 0 can be taken zero or more times.

When two cycles that start and end at the same state use different letters, their sum appears under one star, as in (ab^*b+ba^*a)^*. The expression is valid when every return to the start is made by exactly one of these cycles, and the final part then lists the paths to accepting states.

A trap state is a non-accepting state from which no accepting state can be reached. Any path that enters it contributes nothing, so it is dropped from the expression. When every route back to an accepting state consumes a fixed block of symbols, the loop is a star of that block. If a move to the trap is forbidden except on a two-symbol return, the cycle is (0+11)^*, and the language has the form of a fixed prefix followed by this star.

A parity automaton tracks whether the number of symbols read so far is even or odd. In a two-state DFA that stays put on 0 and switches on 1, the accepted strings are those with an odd number of 1s. The expression 0^*1(0+10^*1)^* reads leading zeros, then one 1, and then blocks that are either a single 0 or contain exactly two 1s, which keep the parity unchanged.

With \epsilon-transitions, first compute the \epsilon-closure of each state, since an \epsilon-move can be taken without reading input. A useful identity when merging alternative cycles is 0^* = (00)^* + 0(00)^*, which lets two routes be combined into one expression.

Regular language closure properties

Regular languages are closed under union, intersection, complement, concatenation, Kleene star and reversal. Closure under complement holds because a complete DFA remains complete when its accepting and non-accepting states are swapped. The minimal DFA of a language has one state for each residual x^{-1}L = \{y \mid xy \in L\}. Complementing L keeps the residual structure and swaps the accepting roles, so the minimal DFA of \overline{L} has the same number of states as that of L. By contrast, union, intersection and concatenation can change the state count, and a change by a finite set can change it sharply. Removing a single string from \Sigma^* needs a DFA with several states, so the minimal size is not preserved under such modifications.

Set equations often give only inclusions. The condition L_1 \cap \overline{L_2} = \emptyset means L_1 \subseteq L_2, and equality L_1 = L_2 would also require L_2 \subseteq L_1. A regular superset can also absorb a non-regular set in a union: since \Sigma^* is regular, \Sigma^* \cup L_3 is regular for every language L_3. Conversely, if the complement of a set were regular, the set itself would be regular, because regular languages are closed under complement.

Hypotheses about intersections constrain the languages only partly. If L_2 is regular and L_1 \cap L_2 is regular, then L_1 itself can be an arbitrary language. Choosing L_2 = \emptyset makes the intersection empty and regular, while L_1 may be non-regular. Only conclusions that follow from the hypotheses are valid, such as the fact that the regular set L_2 is also context-free.

Decidability and undecidable problems

A problem is decidable if some Turing machine halts on every input and gives the correct answer. A decider for a language L halts on every string, accepts every member of L and rejects every string outside L. A recognizer that accepts L may run forever on strings outside L, so the existence of a recognizer does not make a language decidable.

Rice's theorem states that every non-trivial property of the language accepted by a Turing machine is undecidable. A property is a property of the language if any two machines that accept the same language always agree on it, and it is non-trivial if some Turing machines have it and some do not. Equality of two Turing machine languages, regularity of L(M), and the question whether L(M) = \Sigma^* are all such properties, so they are undecidable. Properties that concern the running time of M behave differently. If M must stop within a fixed number of steps on every input, the first steps of each run read only a bounded prefix of the input, so a finite search over short strings decides the question.

For context-free grammars the picture is different. Emptiness of a CFL is decidable by marking the variables that derive terminal strings and checking whether the start variable is marked. Equivalence of two CFGs and emptiness of the intersection of two CFLs are undecidable, which can be shown by a reduction from Post's Correspondence Problem. Equality of a CFL with a regular language is also undecidable, since taking the regular language to be \Sigma^* reduces the question to universality of a CFG.

Context-free and non-context-free language classification

A language is context-free when some context-free grammar or pushdown automaton recognises it. The standard non-context-free examples are \{a^nb^nc^n\} and copy languages such as \{ww\}, which are shown non-context-free by the pumping lemma. Every long string splits as uvwxy with |vx| \ge 1 and |vwx| bounded, and pumping v and x together breaks the required equalities. A single equality between two counts that are nested or sequential is context-free, whereas two equalities that cross each other are not. Because the intersection of two CFLs need not be context-free, a language defined by two context-free conditions can fail to be context-free even when each condition alone is context-free.

The languages \{a^nb^nc^m\} and \{a^mb^nc^n\} are each accepted by a deterministic pushdown automaton, but their intersection \{a^nb^nc^n\} requires two counts to agree with a third, which one stack cannot track. The complement of the copy language \{ww\} is context-free nonetheless. Every odd-length string lies in the complement, and an even-length string uv with |u| = |v| lies outside \{ww\} exactly when u \neq v, which a pushdown automaton can check by guessing the position of the first mismatch.

When the lengths of blocks are tied together, the classification depends on which blocks are linked. In \{a^mb^mc^{m+n} \mid n \ge 1\}, the a and b blocks are linked, and the c block is also linked to them, so pumping breaks the relation and the language is not context-free. The language \{a^mb^nc^{m+n}\} is context-free, because a pushdown automaton pushes for each a and b and pops for each c.

A linear relation among four consecutive blocks can also be context-free when it is a single equation. A constraint such as i+k = j+\ell uses one balance counter, and a stack holding a signed count, restricted to the regular order a^*b^*c^*d^*, can check it. Nested equalities such as i = \ell together with j = k are context-free, while crossing equalities such as i = k together with j = \ell are not.

Recursive and recursively enumerable languages

A language is recursive when some Turing machine decides it, and recursively enumerable (RE) when some Turing machine accepts it, possibly running forever on strings outside the language. Every recursive language is RE, and a language is recursive exactly when both it and its complement are RE. Recursive languages are closed under complement, union and intersection, whereas RE languages are closed under union and intersection but not under complement.

Many automaton questions reduce to decidable checks. For a DFA, emptiness (whether an accepting state is reachable from the start state) and universality (whether the complement is empty) are decidable. For a pushdown automaton, emptiness is decidable, but universality, that is L(M) = \Sigma^*, is undecidable, so the set of encodings of pushdown automata whose language is all strings is not recursive.

For properties of Turing machines themselves, a question such as whether M runs more than a fixed number of steps on every input can be decided. Each run during its first steps reads only a bounded prefix of the input, so simulating M for that many steps on the finitely many inputs of bounded length settles the question. The variant asking whether some input gives a longer run is decided by the same finite search, so both variants are decidable.

Pushdown automata acceptance

A pushdown automaton (PDA) reads an input symbol or \epsilon, looks at the top of its stack, pops that symbol and pushes a string. Acceptance by final state and acceptance by empty stack define the same class of languages, but the empty-stack version relies on a bottom marker \bot. The machine must remove \bot itself, and only \epsilon-moves can do this after the input has been consumed.