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 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 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 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.

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.

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.

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.

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.

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.