Theory of Automata | Theory of Computation & Formal Language

Explore automata basics, including formal versus informal languages, and how alphabets, strings, and words define a language; highlight regular expressions and finite automata as key definitions.

Explore the descriptive definition of languages by showing conditions on words, such as odd length, not starting with a, equal or even counts, and patterns like a^n b^n.

Explore the Kleene star closure and Kleene plus, noting that star includes the null string and yields an infinite language, while plus omits the null string.

Define languages recursively, using the Kleene star closure and plus operation, with base words and construction rules; illustrate via integers from x+1 and x-1 and strings ending in a.

Explore regular expressions, including Kleene star, closure, and plus, and how (a+b)* expresses strings over a and b, with even-length patterns shown by ((a+b)(a+b))*.

Learn how a single language can be defined by multiple regular expressions. See examples over a and over a,b illustrating constraints such as at least one a and one b.

Explore equivalent regular expressions by comparing r1 and r2, review the even language with null string, and see how (a+b)* (aa+bb) and (a+b)* aa plus (a+b)* bb define the same language.

Explore finite automata, a deterministic machine that accepts or rejects input, using states with an initial and final states, a transition diagram or table, and an input alphabet.

Explore equivalent finite automata and how different automata can accept the same language, using strings over {a,b}, and a regex for words starting with b.

Explore languages over {a, b} where one starts with a and other not starting with b, showing how null strings differ in L1 and L2 using FA and regular expressions.

Study languages over {a, b} with three consecutive a's or b's, via a regular expression. Explore the six-state automaton for triple-a or triple-b and the four-state even-language automaton.

Explore finite versus infinite languages and build finite automata for finite sets, including NFAs with dead states. See regex versus descriptive definitions and examples on {a,b}, such as null string, b, ab, bb, and a language not ending in aa or bb, ending in ab or ba.

Explore the transition graph, which supports multiple initial states, a finite input alphabet, and transitions for the null string or substrings like 'aa' or 'ab', with comparisons to finite automata.

Explore five examples that strengthen the concept of transition graphs for languages over {a, b}, linking regular expressions to automata and illustrating patterns like aaa or bbb.

generalized transition graphs extend transition graphs by using regular expressions to define languages over {a, b} like aa or bb, or beginning and ending in same or different letters.

Explore nondeterministic finite automata, contrasting NFAs with DFAs and transition graphs, highlighting multiple paths, a single initial state, and languages containing 'aa' or 'bb'.

Convert an NFA to a DFA by adding an empty state for missing transitions and using composite states when a letter leads to multiple options, as shown in examples.

Explore CFG and CFL, focusing on syntactics in computer languages, and learn CFG components—terminals, non-terminals, productions, and the start symbol s—and how they generate a language.

Explore the context free language by analyzing context free grammar rules, generating strings with productions like S -> aS and S -> null, and illustrating the a-closure language.

Explore more complex CFL examples with S, X, and Y over a and b, distinguishing terminals and non-terminals and deriving (a+b)*. See CFGs for even language and production simplifications.

Explore how trees depict context-free grammars and CFLs, using a derivation from S to AA and A to bA, Ab to generate baab, via a parse tree.

Compare ambiguous and unambiguous context-free grammars through production trees and derivations. See how the word aaa can have multiple derivations in one grammar and a single derivation in another.