نظریه زبان‌ها و ماشین‌هاTheory of Computation

Read off the single count equality each grammar branch enforces, then test a candidate string by comparing letter counts instead of building derivations.

A language is context-free if its only stack obligation is one matching, plus regular filters that closure preserves.

When almost all states accept, count total strings and subtract those that fall into the trap state.

Pick the right boundary string, then show every split uvxyz with vxy <=p can be pumped out of the language.

Simulate the PDA step by step, tracking the stack; accept only if input is fully consumed AND you land in a final state (or empty the stack).

Translate a regular expression into a forbidden-pattern rule, then test a string by structure instead of full parsing.

L/ a = w : wa in L is regular: keep the DFA, only re-mark accepting states.

Finite (bounded) memory like parity stays regular; comparing unbounded counts does not.

A product automaton that advances one component per symbol recognizes the shuffle of the two languages.

Recognize the right-scan + carry-from-the-right pattern that computes x+1 in binary.

Run two DFAs in lockstep on the same input — states are pairs ⟨q1,q2⟩ — then pick the accepting pairs to realize any Boolean combination: AND for ∩, OR for ∪, XOR for symmetric difference, AND-NOT for set difference.

Rip out states one by one, rerouting their paths into edge labels, until only start and accept remain; what's left on that edge is the regular expression — Arden's rule does the same job algebraically.

Regular languages are closed under every standard operation — union, intersection, complement, concatenation, star, reversal, homomorphism — but a countably infinite union of regular languages need not be regular.

Every regular language has a pumping length p such that any long string splits as xyz with y pumpable; find one long string whose every legal split breaks membership, and the language cannot be regular.

One stack = exactly the CFLs; TWO independent stacks = a full Turing machine. The number of stacks, not the fancy access rules, is what jumps you past context-free.

An NFA accepts a string iff at least one choice of transitions ends in an accepting state — track the whole set of reachable states symbol by symbol instead of guessing one lucky path.

Linear = at most ONE nonterminal per rule body. They sit strictly between regular and context-free, and are closed under union, reversal and homomorphism but NOT under intersection, complement or concatenation.

Convert any (epsilon-)NFA to an equivalent DFA whose states are sets of NFA states — then, if the question asks for the minimum number of states, minimize the result rather than reporting the raw subset count.

Adding a Stay option keeps a TM at full recursively-enumerable power, but forbidding the head from re-scanning what it already passed collapses it: a head that can never (or only once) move back toward the start reads each cell at most once and recognizes only regular languages.

A <=T B means a decider for A exists given an oracle for B. Solvability flows OPPOSITE the arrow (B easy => A easy), <=T is a preorder not a partial order (mutual reduction gives Turing-equivalence, not equality), and oracles are closed under complement, so A <=T A^c always.

A CFG is ambiguous iff some string has two distinct leftmost derivations (equivalently, two distinct parse trees) — exhibit ONE such string to prove it. Ambiguity is a property of the grammar, not the language: two grammars can generate the same language while one is ambiguous and the other unambiguous, as the classic dangling-else grammar shows.

The empty language and every finite language are regular, so a non-regular language must be infinite and nonempty. Two cheap regular subsets sit inside ANY language L: the empty set, and any finite subset you pick. Use these facts to instantly kill exam claims like 'some language has no regular subset' or 'a non-regular language could be finite'.

Ambiguity is a property of a grammar (a string with ≥ 2 parse trees); inherent ambiguity is a property of a language (every grammar for it is ambiguous). These nest into a strict chain RegularsubsetneqDCFLsubsetneqUnambiguous CFLsubsetneqCFL : every deterministic CFL is unambiguous, but some CFLs are inherently ambiguous and lie outside even the unambiguous class.

Drop ε-transitions and force one accepting state, and if ε∈L the start must equal that accepting state — which forces every accepted string to loop back, making L closed under concatenation.

L is RE iff it is the DOMAIN of a partial computable function, iff it is the RANGE of one (or empty), iff it is enumerable. RE is closed under finite union/intersection, concatenation, star, homomorphism, and EFFECTIVE countable union (dovetailing) — but NOT under complement nor arbitrary countable union.

Over a one-letter alphabet the language hierarchy collapses: every context-free L over a single symbol is already regular. This follows from Parikh's theorem (CFL Parikh images are semilinear, and over a unary alphabet the Parikh image IS the language, so the set of lengths is eventually periodic = regular). It does NOT say arbitrary subsets of a^ are regular.

Recognize "strings that avoid a fixed pattern" with a DFA that tracks the longest matched prefix of the pattern and drops into an absorbing non-accepting trap state the instant the whole pattern appears.