Automata Theory | Theory of Computation Beginner to advanced

Extend the transition function to strings; the extended transition function maps a state q and input string w to the final state p, denoted delta cap, with a DFA example.

Design a finite automaton that accepts strings over a's and b's starting with ab, with q0 as start, q2 final after ab, and q3 as a dead state.

Design a three-state finite automaton that accepts all strings of a's and b's ending with aa, starting at q0 and final at q2.

Design an fa that accepts strings over a and b starting and ending with the same symbol, by combining automata for start-a end-a and start-b end-b with an or operation.

Design a finite automaton over a and b that accepts strings with exactly two a's, with any number of b's around them, and at most two a's via final states.

Design a DFA that accepts strings with an odd number of zeros and an even number of ones using the Cartesian product of two DFAs, final state q1q2.

Design an fa over a and b to accept length three using q0 to q3. Extend to accept at least three and at most three with states; avoid infinite loops.

Explore nondeterministic finite automata and contrast them with DFAs, highlighting that NFAs allow multiple, zero, or one transitions per input and use the power set 2^Q as the transition set.

Show how the extended transition function computes possible NFA states by uniting transitions for each input symbol and epsilon moves, with a step-by-step example.

Convert an NFA to a DFA using a transition table, starting from the initial state q0 and forming new states like {q0,q1}, {q0,q1,q2}, and {q0,q2}.

Demonstrate the equivalence of deterministic and nondeterministic finite automata by constructing a DFA from an NFA via subset construction, proving L(D) = L(N) using the extended transition function.

Explore the concept of epsilon closure, the set of states reachable from a given state by consuming only epsilon transitions, shown with q0, q1, and q2.

Design a Moore machine that counts occurrences of the substring aab, outputting 1 for each found instance and 0 otherwise, using states q0 through q3.

Design a mealy machine that outputs the 1's complement of a binary input, using a single state to map 1 to 0 and 0 to 1, demonstrated on sample inputs.

Explore two-way deterministic finite automata (2DFA) where the tape head moves left or right and acceptance occurs when it moves off the right end into a final state.

Learn to build regular expressions for languages over a and b, including starting with a or ab, containing aba, and start and end with same symbol, using union and concatenation.

Convert regular expressions to epsilon NFAs by creating initial and final states and using epsilon transitions to support union, concatenation, and star operations.

Construct an epsilon NFA for ab and for a, then combine them with union and extend to ab union a star using epsilon transitions, including start and final state adjustments.

Demonstrate that every regular expression defines a language also recognized by an epsilon NFA, via constructive proofs for basic and combined expressions, establishing language equivalence with finite automata.

Convert a DFA to a regular expression using Arden's theorem, deriving expressions like R = Q P star and building expressions for states A, B, and C.

Derive a regular expression for the given DFA by solving state equations, expressing the final state D as ac or c c star b c or c c star a.

Explore how the pumping lemma proves certain languages are not regular by decomposing strings into x y z with y nonempty and pumping y.

Apply pumping lemma to the language of n zeros followed by n ones, proving it is not regular by examining cases where pumped part contains zeros, ones, or both.

Explore how regular languages are closed under union, concatenation, and star, with proofs via regular expressions and DFAs. See closure under complementation, intersection, difference, reversal, homomorphism, and inverse homomorphism.

Explore how a context-free grammar defines a context-free language with V, T, P, and S, including non-terminals, terminals, and productions, then derive strings like ab from the start symbol.

Design a context-free grammar for the language w c w^R, where w is in {0,1}*, using productions that mirror w around the center c.

Design a context-free grammar that generates balanced parentheses by using productions such as S -> ( S ) and S -> S S, with epsilon to stop.

Design a context-free grammar for strings with equal numbers of a's and b's, generating minimal strings such as ab or ba and longer ones like abbaba using epsilon rules.

Follow leftmost and rightmost derivations in a grammar for balanced parentheses by replacing the leftmost variable or the rightmost S, respectively.

Construct parse trees to represent how a string derives from a grammar, with each node labeled by a variable and leaves as terminals or epsilon, whose yield equals the string.

Explore ambiguous grammar in context-free grammars, where a string like aaa has multiple leftmost and rightmost derivations, showing how choosing different productions leads to ambiguity.

Explore decision problems for context-free languages, including emptiness, finiteness, and membership, with methods to determine generating start symbols, analyze cycles, and simulate pushdown automata.

Apply the pumping lemma for context-free languages to show that a^n b^n c^n is not context-free. Split z into u v w x y and pump v and x.