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.

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.

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

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.