CSCD 420 Oct 15 2026

Overview

Chris Cain reviews regular expressions and context-free grammar construction, emphasizing how to encode exact or bounded symbol counts, inequalities between counts, language operations, and modular string lengths. The class then connects lambda-NFA subset construction with regular grammars, working through exam-oriented methods for handling lambda transitions and converting left- or right-linear productions into automata.

Key takeaways

Exact symbol counts in regular expressions require excluding that symbol from every wildcard section; otherwise the expression may accidentally admit extra occurrences.
Optional-symbol positions provide a direct construction for “at most k” occurrences: use k slots, each offering the symbol or λ, with other alphabet symbols between slots.
A grammar for AⁿBᵐ with n > m can generate matched A/B pairs recursively but must terminate with at least one extra A.
Language operations can often be simplified before constructing a grammar: L1 ∪ L2 equals L1 when L2 ⊆ L1, and L1 minus the complement of L4 equals L4 when L4 ⊆ L1.
Lambda-NFA conversion must compute λ-reachable states both when forming the DFA’s initial state and after each consumed input symbol.
Right-linear grammars translate to NFAs by making nonterminals states and expanding multi-symbol terminal sequences into intermediate states; left-linear grammars require reversing the construction direction.

Chapters

0:00 Regular Expressions for Exactly Two A’s

For strings over {A, B, C} containing exactly two A’s, place two required A symbols in the expression.
Use arbitrary-length repetitions of B or C before, between, and after those A’s.
Exclude A from the surrounding repetitions so the expression cannot generate a third A.

2:00 Encoding at Most Three A’s with Optional Symbols

Build three possible A positions, each written as A or λ, with arbitrary B/C strings between positions.
Choosing λ in all three positions generates strings with no A’s; choosing one or more A alternatives gives up to three.
Multiple derivations may generate the same string, but ambiguity does not change the language recognized.

5:00 Requiring A, B, and C in Any Order

Represent arbitrary substrings over {A, B, C} with the shorthand Σ*.
Enumerate all six possible first-occurrence orders of A, B, and C, such as A-B-C and C-B-A.
For each order, concatenate Σ* sections around the required symbols, then union the six expressions.

8:40 Starting the Grammar Practice Set

Cain gives students time to work through grammar-construction exercises before discussing solutions.
The problems are general grammars, not necessarily regular grammars, matching the scope of the first assignment.
The class shifts from regex design to identifying constraints that a grammar must enforce.

18:00 A Grammar for More A’s Than B’s

For strings in the form AⁿBᵐ with n > m, the grammar must preserve the order of all A’s before all B’s.
Use recursive productions that add a matched A/B pair while maintaining at least one extra A.
A separate terminating step must produce at least one A, preventing derivations with equal counts.

23:00 Constructing Star Closure Without Invalid Derivations

To generate L1*, allow completed L1 strings to repeat by returning to the start of the L1 construction.
Separate the choice of producing zero repetitions (λ) from the recursive process that generates a valid L1 string.
Putting λ directly on the count-preserving recursion can incorrectly permit equal numbers of A’s and B’s within a nonempty repetition.

29:00 Simplifying Grammar Union and Complement Expressions

For L1 ∪ L2, create a new start symbol with alternatives to the start symbols for each language, keeping nonterminal names distinct.
If L2 is a subset of L1, the union simplifies to L1 and a separate L2 grammar is unnecessary.
When L4 is a subset of L1, L1 minus the complement of L4 reduces to L4, avoiding a more complicated grammar construction.

35:00 Grammar Rules for Concatenation, Powers, and Modulo Lengths

For concatenation L1L2, use a new start production that places the L1 grammar’s start symbol before the L2 start symbol.
For L1³, concatenate three copies of the L1 start symbol in the new start production.
For strings of A’s whose length is nonzero modulo 3, recurse in groups of three A’s and terminate with either one or two additional A’s.

40:00 Converting a Lambda-NFA by Tracking State Sets

In subset construction, include every state reachable through λ-transitions without consuming an input symbol.
A λ-edge from Q0 to final state Q2 makes the DFA start state the set {Q0, Q2}, which is accepting.
When processing an A, follow A-edges from every state in the current set and include λ-reachable states; missing transitions lead to the trap state.

46:00 Converting Linear Grammars into NFAs

A right-linear grammar maps nonterminals to states; terminal sequences longer than one symbol are expanded into intermediate states.
A production with a terminal followed by the same nonterminal creates a labeled self-loop, while a terminating production leads to a final state.
For a left-linear grammar, reverse the construction direction, beginning from a final state and working back toward the start state.
A grammar must consistently keep its nonterminal on the right or left to be linear; an inconsistent production is not a regular grammar rule.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Chris Cain.