Alphabet (Σ): A finite, non-empty set of symbols. Example: Σ = {0, 1} (binary alphabet).

String: A finite sequence of symbols chosen from an alphabet. Example: w = 0101 is a string over Σ = {0, 1}.

Language (L): A set of strings all of which are chosen from some Σ*. Example: L = {0, 00, 000} is a language over {0}.

Finite vs Infinite Language: A finite language contains a countable, bounded number of strings (e.g., L = {a, aa}). An infinite language contains an unbounded number of strings (e.g., L = {a^n | n ≥ 0}).

Limitations of Sequential Circuits: They have finite memory (finite number of states) and cannot recognize context-free or context-sensitive languages (like a^n b^n) which require an unbounded memory structure like a stack or an infinite tape.

Applications of Grammars: Primarily used in compiler design (syntax analysis and parsing), natural language processing, describing programming language syntax (using BNF or EBNF formats), and formally specifying network protocols.

We are designing a Finite State Machine to detect the sequence "1101". We will define the states based on the prefix of the sequence successfully matched so far:

• A (initial): No part of the sequence matched.
• B: "1" matched.
• C: "11" matched.
• D: "110" matched.

State Transition Table (Mealy Machine Formulation):

Present State	Input = 0 (Next State, Output)	Input = 1 (Next State, Output)
A	A, 0	B, 0
B	A, 0	C, 0
C	D, 0	C, 0
D	A, 0	B, 1

Explanation of overlap handling: From state D (we have seen "110"), an input of '1' completes the sequence "1101", yielding an output of 1. Because overlapping is allowed, this final '1' can serve as the first '1' of a new sequence, so the next state transitions to B instead of A.

k-equivalent states: Two states q_1 and q_2 are k-equivalent if, for every input string w of length ≤ k, the machine produces the exact same output sequence when started in q_1 as it does when started in q_2. If two states are k-equivalent for all k, they are deemed strictly equivalent and can be merged.

Lossy vs Lossless Machine: A lossless machine is one where the input sequence can be uniquely and entirely determined by examining the initial state and the resulting output sequence. A lossy machine loses information during transitions, meaning you cannot reconstruct the original input from just the output and start state.

Minimization by Partitioning (Myhill-Nerode Theorem Approach):

1. 0-equivalence (P0): Partition all states into blocks based solely on their outputs. (e.g., all states that output 0 go to Block 1, all that output 1 go to Block 2).
2. 1-equivalence (P1): For each block in P0, partition it further if the next states for identical inputs go to different blocks in P0.
3. k-equivalence (Pk): Repeat the partitioning process using the blocks from P(k-1). Stop when P_k = P_{k-1}. The resulting blocks represent the minimized states.

The core difference between the two finite state transducers lies in how outputs are generated:

• Mealy Machine: The output depends on both the present state and the present input symbol. Outputs are associated with the transition edges. Because of this, Mealy machines generally require fewer states, but their outputs react asynchronously/immediately to input changes.
• Moore Machine: The output depends only on the present state. Outputs are associated directly with the state nodes. Moore machines generally require more states to model the same logic, but their outputs are perfectly synchronous with state changes.

To convert a Mealy machine to an equivalent Moore machine, we must shift the outputs from the transitions to the states themselves. The standard procedure is:

1. Calculate the number of incoming transitions for every state in the Mealy machine and note the output associated with each transition.
2. If a state q_i is entered by transitions that have different outputs (e.g., some produce 0, some produce 1), split the state into multiple states in the Moore machine: q_{i0} (which outputs 0) and q_{i1} (which outputs 1).
3. If a state is entered by transitions that all have the same output, the state does not need to be split. Assign that output to the state.
4. Route all incoming transitions to the corresponding newly split states based on their outputs.
5. Duplicate the outgoing transitions from the original state to all of its new split states.
6. If the initial state has no incoming transitions, it can be assigned an arbitrary default output (usually 0).

Arden's Theorem: Let P and Q be two regular expressions. If P does not contain the null string (λ or ε), then the equation R = Q + RP has a unique solution given by R = QP^*.

Proof Outline:
Substitute R = QP^* into the RHS:
Q + RP = Q + (QP^*)P = Q + QP^*P = Q(\epsilon + P^*P) = QP^* = R.

Kleene Closure (L*): The set of all strings that can be formed by concatenating zero or more strings from L. It always includes the empty string ε.
Example: If L = {a}, L* = {ε, a, aa, aaa, ...}

Positive Closure (L+): The set of all strings that can be formed by concatenating one or more strings from L. It does not include ε unless ε is already in L.
Example: If L = {a}, L+ = {a, aa, aaa, ...}

Closure Properties: Regular languages are closed under Union, Intersection, Concatenation, Kleene Closure, Complement, Homomorphism, and Reversal.

Homomorphism: A substitution where a single symbol from an alphabet is replaced by a string (or another symbol). If h is a homomorphism, then h(L) is the language obtained by applying h to every string in L.

Solution:
String 1: w = aa → h(aa) = h(a)h(a) = (ab)(ab) = abab
String 2: w = aba → h(aba) = h(a)h(b)h(a) = (ab)(bbc)(ab) = abbbcab
Homomorphic Image h(L) = \{abab, abbbcab\}

Regular Expression: (0+1)^*00

DFA Design: We need 3 states to track the ending sequence.

• q0: Initial state (no 0s seen yet)
• q1: One 0 seen at the end
• q2: Two 0s seen at the end (Final State)

Present State	Input 0	Input 1
→ q0	q1	q0
q1	* q2	q0
* q2	* q2	q0

Pumping Lemma for Regular Languages: If L is a regular language, there exists a pumping length 'p' such that any string w ∈ L with |w| ≥ p can be split into three parts, w = xyz, satisfying:

1. |y| > 0
2. |xy| ≤ p
3. For all i ≥ 0, xy^iz \in L

Proof by Contradiction:
1. Assume L is regular. Let 'p' be the pumping length.
2. Choose a string w = a^p b^p. Clearly w \in L and |w| = 2p \ge p.
3. Let w = xyz. Since |xy| \le p, the substring 'y' must consist entirely of 'a's. Let y = a^k where k > 0.
4. By the pumping lemma, pumping 'y' zero times (i = 0) should yield a string in L. So xy^0z = xz must be in L.
5. However, removing 'y' decreases the number of 'a's by k, but leaves the number of 'b's unchanged. The new string is a^{p-k} b^p.
6. Since p-k \neq p, this string is NOT in L. This is a contradiction. Therefore, L is not regular.

The language requires an even number of 'a's followed by an odd number of 'b's.

• Even number of 'a's: (aa)^*
• Odd number of 'b's: b(bb)^*

Regular Expression: (aa)^* b(bb)^*

Chomsky Hierarchy & Automata:

Type	Grammar / Language	Recognizing Automaton	Production Rule Constraints
Type-0	Recursively Enumerable	Turing Machine (TM)	α → β (No restrictions, α must contain at least one non-terminal)
Type-1	Context-Sensitive (CSL)	Linear Bounded Automaton (LBA)	αAβ → αγβ (or |α| \le |β|)
Type-2	Context-Free (CFL)	Pushdown Automaton (PDA)	A → γ (LHS is exactly one non-terminal)
Type-3	Regular Language (RL)	Finite State Automaton (FSA)	A → aB or A → a (Strictly Right or Left Linear)

Ambiguity: A Context-Free Grammar is ambiguous if there exists at least one string in its generated language that has more than one valid Leftmost Derivation (LMD), more than one Rightmost Derivation (RMD), or consequently, more than one distinct Parse Tree.

LMD vs RMD:

• Leftmost Derivation: At each step of the derivation, the leftmost non-terminal in the sentential form is replaced.
• Rightmost Derivation: At each step of the derivation, the rightmost non-terminal is replaced.

Intersection of CFLs: CFLs are NOT closed under intersection. Proof by counter-example:
Let L_1 = \{a^n b^n c^m | n,m \ge 0\} (CFL, match a's and b's using stack).
Let L_2 = \{a^m b^n c^n | n,m \ge 0\} (CFL, match b's and c's using stack).
Their intersection is L_1 \cap L_2 = \{a^n b^n c^n | n \ge 0\}, which is a known Context-Sensitive Language, NOT a Context-Free Language. Thus, CFLs are not closed under intersection.

Unit Production: A production rule of the form A → B, where both A and B are single non-terminals. They chain derivations without producing terminal symbols.

Removal of Unit Productions:
Given: S → AB, A → a, B → C, C → D, D → b
Identify unit pairs: (B,C), (C,D), and transitively (B,D).
Since D derives 'b', C also derives 'b', and B also derives 'b'.
Simplified Grammar: S → AB, A → a, B → b, C → b, D → b. (C and D can then be removed if unreachable from S).

Useless Productions: Productions containing non-terminals that are either non-generating (cannot derive a terminal string) or non-reachable (cannot be reached from the start symbol S).

Chomsky Normal Form (CNF): A CFG is in CNF if all its production rules are of the form:
1. A → BC (A non-terminal derives exactly two non-terminals)
2. A → a (A non-terminal derives exactly one terminal)
(Any CFG without ε-productions can be converted to CNF, and every parse tree in CNF is a strict binary tree).

Greibach Normal Form (GNF): A CFG is in GNF if all its production rules are of the form:
A → a\alpha
where 'a' is a single terminal and 'α' is a sequence of zero or more non-terminals. This guarantees that every derivation step consumes exactly one terminal, making it highly suitable for PDA construction.

Pushdown Automaton (PDA): A finite automaton equipped with a stack (LIFO memory). It is mathematically defined as a 7-tuple: M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F), where \Gamma is the stack alphabet and Z_0 is the initial stack symbol. PDAs recognize Context-Free Languages.

DPDA vs NPDA:

• Deterministic PDA (DPDA): For any given state, input symbol (or ε), and top of stack symbol, there is at most one transition defined. DPDAs recognize a strict subset of CFLs (Deterministic CFLs), such as a^n b^n or wcw^R.
• Nondeterministic PDA (NPDA): Can have multiple valid transitions for the same configuration. NPDAs are strictly more powerful than DPDAs and recognize all Context-Free Languages (e.g., ww^R which requires guessing the midpoint).

A PDA can accept a string in two distinct ways (which are proven to be equivalent in power for NPDAs):

1. Acceptance by Final State: The PDA reads the entire input string and ends up in one of its designated accepting states (F), regardless of what is left on the stack.
2. Acceptance by Empty Stack: The PDA reads the entire input string and the stack becomes completely empty (even the initial Z_0 is popped). The state it ends in does not matter.

Turing Machine: The most powerful computational model, consisting of a finite state control, an infinite tape divided into cells, and a read/write head that can move left or right. It recognizes Recursively Enumerable languages and models any computable function (Church-Turing Thesis).

Halting Problem: The problem of determining, given a description of an arbitrary computer program and an input, whether the program will eventually halt (finish running) or continue to run forever.

Proof of Undecidability:
Assume there exists a TM H(M, w) that decides the Halting Problem: it outputs "Halt" if M halts on w, and "Loop" if M loops on w.
Now construct a paradoxical machine D that takes a machine description M as input. D simulates H(M, M):
- If H says M halts on M, D purposely goes into an infinite loop.
- If H says M loops on M, D immediately halts.
What happens if we feed D to itself, i.e., run D(D)?
- If D(D) halts, H must have output "Halt", meaning D should loop. Contradiction.
- If D(D) loops, H must have output "Loop", meaning D should halt. Contradiction.
Since D results in a logical paradox, the assumed decider H cannot exist. Therefore, the Halting problem is undecidable.

Church-Turing Thesis: A fundamental hypothesis stating that any intuitive or algorithmic computation can be performed by a Turing Machine. If a problem cannot be solved by a TM, it cannot be solved by any physically realizable computing device.

Universal Turing Machine (UTM): A specific Turing Machine that can simulate the behavior of any other Turing Machine. It takes as input the encoding of a machine M and an input string w, and executes M on w. It forms the theoretical basis for the modern programmable stored-program computer (von Neumann architecture).

Step 1: Eliminate ε-productions and unit productions.
The given grammar has no ε-productions and no unit productions.

Step 2: Replace mixed terminals with new non-terminals.
Let X → 1 and Y → 0.
S → XA | YB
A → XAA | YS | 0
B → YBB | XS | 1

Step 3: Restrict to two non-terminals on LHS.
In A → XAA, replace AA with Z_1 where Z_1 → AA.
In B → YBB, replace BB with Z_2 where Z_2 → BB.

Final CNF Grammar:
S → XA | YB
A → XZ₁ | YS | 0
B → YZ₂ | XS | 1
Z₁ → AA
Z₂ → BB
X → 1
Y → 0

Proof by Contradiction:
1. Assume L is regular. Let p be the pumping length.
2. Choose w = a^{p^3}. Clearly w \in L and |w| = p^3 \ge p.
3. By Pumping Lemma, w = xyz where |xy| \le p and |y| > 0.
Let |y| = k, so 1 \le k \le p.
4. Pump y twice (i=2). The length of the new string is |xy^2z| = p^3 + k.
5. We know k \le p, so the new length p^3 + k \le p^3 + p.
6. The next perfect cube after p^3 is (p+1)^3 = p^3 + 3p^2 + 3p + 1.
7. Since p \ge 1, p^3 < p^3 + k \le p^3 + p < p^3 + 3p^2 + 3p + 1.
8. Therefore, p^3 + k is strictly between two consecutive perfect cubes, so it cannot be a perfect cube itself. Thus a^{p^3+k} \notin L, contradicting the lemma. L is not regular.

We use a Finite State control with 4 states to track the parity. The TM simply sweeps from left to right without modifying the tape.

• q0 (Initial/Final): Even 0s, Even 1s
• q1: Odd 0s, Even 1s
• q2: Even 0s, Odd 1s
• q3: Odd 0s, Odd 1s

Transitions (State, Read → Write, Move, Next State):
q0, 0 → 0, R, q1
q0, 1 → 1, R, q2
q1, 0 → 0, R, q0
q1, 1 → 1, R, q3
q2, 0 → 0, R, q3
q2, 1 → 1, R, q0
q3, 0 → 0, R, q2
q3, 1 → 1, R, q1

Upon reading a Blank (B) while in state q0, the TM transitions to a Halting Accept state. If it reads a Blank in q1, q2, or q3, it transitions to a Reject state.

The logic is simple: Push an 'a' onto the stack for every 'a' read from input. Then, pop an 'a' from the stack for every 'b' read. If the stack is empty exactly when the input ends, accept.

Transitions:

• δ(q_0, a, Z_0) = \{(q_0, aZ_0)\} (Push first 'a')
• δ(q_0, a, a) = \{(q_0, aa)\} (Push subsequent 'a's)
• δ(q_0, b, a) = \{(q_1, \epsilon)\} (Read first 'b', pop 'a', switch to state q1)
• δ(q_1, b, a) = \{(q_1, \epsilon)\} (Read subsequent 'b's, pop 'a')
• δ(q_1, \epsilon, Z_0) = \{(q_2, \epsilon)\} (Input finished, pop Z0 to empty stack, accept)

An NPDA must "guess" the midpoint of the string because it does not know where the first half ends and the second half begins.

• State q0 (Pushing half): Push every symbol read onto the stack.
• State q1 (Popping half): Pop a symbol if it matches the current input symbol.

Transitions:
δ(q_0, a, X) = \{(q_0, aX)\} (Push a)
δ(q_0, b, X) = \{(q_0, bX)\} (Push b)
δ(q_0, \epsilon, X) = \{(q_1, X)\} (NON-DETERMINISTIC GUESS: Transition to popping phase without consuming input)
δ(q_1, a, a) = \{(q_1, \epsilon)\} (Match a)
δ(q_1, b, b) = \{(q_1, \epsilon)\} (Match b)
δ(q_1, \epsilon, Z_0) = \{(q_{acc}, \epsilon)\} (Accept by empty stack)

Step 1: Ensure A_i → A_j has i < j.
Substitute A2 in A1:
A_1 → A_3 A_1 A_3 | b A_3
Substitute A1 in A3:
A_3 → (A_3 A_1 A_3 | b A_3) A_2 | a
A_3 → A_3 A_1 A_3 A_2 | b A_3 A_2 | a

Step 2: Eliminate Left Recursion on A3.
Let Z be a new non-terminal to handle the recursive part A_1 A_3 A_2.
A_3 → b A_3 A_2 | a | b A_3 A_2 Z | a Z
Z → A_1 A_3 A_2 | A_1 A_3 A_2 Z

Step 3: Back-substitute A3 to put all rules in GNF.
Since A3 now only starts with terminals 'b' and 'a', we substitute A3 into A2 and A1, achieving complete Greibach Normal Form where every production starts with exactly one terminal.

Step 1: Solve for B.
B → x | Bw is equivalent to equation B = Bw + x. Using Arden's Theorem (R = Q + RP → R = QP*), we get: B = x w^*.

Step 2: Solve for C.
C = y.

Step 3: Solve for A.
A = By + Cw = (x w^*)y + (y)w = x w^* y + y w.

Step 4: Solve for S.
S = Ax + By = (x w^* y + y w)x + (x w^*)y = x w^* y x + y w x + x w^* y.

Final RE: x w^* y x + y w x + x w^* y

State Table (Mealy Machine):
States: S0 (Initial), S1 ("0"), S2 ("01"), S3 ("010")

Present State	Input x=0 (Next, Out)	Input x=1 (Next, Out)
S0 (00)	S1, 0	S0, 0
S1 (01)	S1, 0	S2, 0
S2 (10)	S3, 0	S0, 0
S3 (11)	S1, 0	S2, 1 (0101 detected!)

State Assignment: Let S0=00, S1=01, S2=10, S3=11.
Using D flip-flops (D1 for MSB, D0 for LSB) and input X.
Next state D1 = Σm(1, 3, 7) = X' Q0 + X Q1 Q0
Next state D0 = Σm(0, 2, 6) = X'
Output Y = Σm(7) = X Q1 Q0
Circuit: Consists of two D flip-flops, AND gates, and OR gates implementing these boolean expressions.

We need at least four 'a's, followed by any number of 'a's, followed by at most three 'b's.

• n \ge 4 is represented by aaaa(a)^*
• m \le 3 means zero, one, two, or three 'b's: (\epsilon + b + bb + bbb)

Final Regular Expression: aaaaa^* (\epsilon + b + bb + bbb)

Since l + m = n, every 'c' at the end must be matched by either an 'a' at the beginning or a 'b' in the middle. The strings take the form a^l b^m c^m c^l.

Grammar Rules:
S → aSc \ | \ A (This generates a^l A c^l)
A → bAc \ | \ \epsilon (This generates b^m c^m inside)

Algorithm:
1. Read '0' from tape, replace it with 'X'. Move Right.
2. Scan right over 0s and Ys until finding the first '1'.
3. Replace '1' with 'Y'. Move Left.
4. Scan left over Ys and 0s until finding the rightmost 'X'. Move one step Right (to the next 0).
5. Repeat this process until all 0s are replaced by Xs and all 1s by Ys. If no 0s are left, scan right to ensure no 1s are left. If only blanks (B) are found, Accept.

Transitions:
δ(q0, 0) = (q1, X, R)
δ(q1, 0) = (q1, 0, R), δ(q1, Y) = (q1, Y, R)
δ(q1, 1) = (q2, Y, L)
δ(q2, Y) = (q2, Y, L), δ(q2, 0) = (q2, 0, L)
δ(q2, X) = (q0, X, R)
δ(q0, Y) = (q3, Y, R) (Checking phase)
δ(q3, Y) = (q3, Y, R)
δ(q3, B) = (q_{acc}, B, R) (Accept!)

This grammar is ambiguous because it does not enforce operator precedence (* over +) or associativity (left-associative). We must rewrite it by introducing new non-terminals (T for Terms, F for Factors).

Unambiguous Grammar:
E → E + T \ | \ T (Handles left-associative addition)
T → T * F \ | \ F (Handles left-associative multiplication, with higher precedence)
F → (E) \ | \ a (Handles parentheses and atomic values)

NPDA Transitions (using top-down parsing):
1. δ(q, \epsilon, S) = \{(q, aSa), (q, bSb), (q, c)\} (Expand Non-terminals)
2. δ(q, a, a) = \{(q, \epsilon)\} (Match terminals)
3. δ(q, b, b) = \{(q, \epsilon)\}
4. δ(q, c, c) = \{(q, \epsilon)\}

ID trace for "abcba":
(q, abcba, S)
⊢ (q, abcba, aSa) (Expanded S → aSa)
⊢ (q, bcba, Sa) (Matched 'a')
⊢ (q, bcba, bSba) (Expanded S → bSb)
⊢ (q, cba, Sba) (Matched 'b')
⊢ (q, cba, cba) (Expanded S → c)
⊢ (q, ba, ba) (Matched 'c')
⊢ (q, a, a) (Matched 'b')
⊢ (q, \epsilon, \epsilon) (Matched 'a', Accepted by empty stack!)

Subset Construction Method:

• Start state: A = {q0}
• δ(A, 0) = {q0, q1} = B
• δ(A, 1) = {q2} = C (Final, contains q2)
• δ(B, 0) = δ({q0,q1}, 0) = {q0,q1} ∪ {q2} = {q0, q1, q2} = D (Final)
• δ(B, 1) = δ({q0,q1}, 1) = {q2} ∪ {q1} = {q1, q2} = E (Final)
• δ(C, 0) = δ({q2}, 0) = {q1} = F
• δ(C, 1) = δ({q2}, 1) = {q2} = C
• δ(D, 0) = δ({q0,q1,q2}, 0) = {q0,q1,q2} = D
• δ(D, 1) = δ({q0,q1,q2}, 1) = {q2,q1,q2} = E
• δ(E, 0) = δ({q1,q2}, 0) = {q2,q1} = E
• δ(E, 1) = δ({q1,q2}, 1) = {q1,q2} = E
• δ(F, 0) = δ({q1}, 0) = {q2} = C
• δ(F, 1) = δ({q1}, 1) = {q1} = F

The resulting DFA has 6 states (A through F), where C, D, and E are the accepting final states.

Left Linear Grammar: All productions are of the form A → Bx or A → x (Non-terminal is always on the left).
Right Linear Grammar: All productions are of the form A → xB or A → x (Non-terminal is always on the right).

Grammar for Binary Palindromes (CFG):
A palindrome reads the same forwards and backwards. We generate it from the center outwards.
S → 0S0 \ | \ 1S1 \ | \ 0 \ | \ 1 \ | \ \epsilon

Myhill-Nerode Theorem: A language L over alphabet \Sigma is regular if and only if the equivalence relation R_L defined on \Sigma^* has a finite number of equivalence classes (the index of R_L is finite).
The relation x \ R_L \ y holds if and only if for all z \in \Sigma^*, xz \in L implies yz \in L, and vice versa. This theorem is the foundation for DFA state minimization.

The regular expression requires any number of 'a's, followed by at least one 'b', followed by any combination of 'a's and 'b's.

Right-Linear Grammar Rules:
S → aS \ | \ bA (Starts with a's, transitions to A upon reading 'b')
A → aA \ | \ bA \ | \ \epsilon (After the first 'b', accepts any string)

States track how many 'a's have been seen consecutively at the end of the string.

• q0: 0 consecutive 'a's
• q1: 1 consecutive 'a'
• q2: 2 consecutive 'a's
• q3 (Final): 3 consecutive 'a's

Transitions:
δ(q0, a)=q1, δ(q0, b)=q0
δ(q1, a)=q2, δ(q1, b)=q0
δ(q2, a)=q3, δ(q2, b)=q0
δ(q3, a)=q3, δ(q3, b)=q0

The PDA must match the number of 'a's and 'c's, completely ignoring the count of 'b's in the middle.

Transitions:
1. δ(q_0, a, Z_0) = \{(q_0, aZ_0)\} (Push first 'a')
2. δ(q_0, a, a) = \{(q_0, aa)\} (Push all subsequent 'a's)
3. δ(q_0, b, a) = \{(q_1, a)\} (Read first 'b', don't pop 'a')
4. δ(q_1, b, a) = \{(q_1, a)\} (Read all 'b's, skip stack)
5. δ(q_1, c, a) = \{(q_2, \epsilon)\} (Read first 'c', pop 'a')
6. δ(q_2, c, a) = \{(q_2, \epsilon)\} (Read all 'c's, pop 'a's)
7. δ(q_2, \epsilon, Z_0) = \{(q_3, \epsilon)\} (Accept by Empty Stack)

The NFA needs to non-deterministically guess when the specific "00" substring begins.

• q0 (Initial): Loops on 0 and 1. On input 0, can non-deterministically transition to q1.
• q1: Needs a 0 to transition to q2.
• q2 (Final): Loops on 0 and 1 indefinitely.

Transitions:
δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q0}
δ(q1, 0) = {q2}
δ(q2, 0) = {q2}, δ(q2, 1) = {q2}

The language is all strings that start with '0' and end with '1'.

States: q0 (Initial), q1 (Seen starting 0), q2 (Seen ending 1, Final), q_dead (Started with 1)

Transitions:
δ(q0, 0)=q1, δ(q0, 1)=q_dead
δ(q1, 0)=q1, δ(q1, 1)=q2
δ(q2, 0)=q1, δ(q2, 1)=q2
δ(q_dead, 0)=q_dead, δ(q_dead, 1)=q_dead

This is the union of two conditions. A string is accepted if it matches condition A (starts with 01) OR condition B (ends with 01).

If the string starts with '0' then '1', it falls into an accepting trap state where all further inputs are accepted (since condition A is met). If it does not start with 01, it must be tracked strictly for ending in 01.

The language consists of two independent context-free components concatenated together: a^n b^n and c^m d^m.

Grammar Rules:
S → AB
A → aAb \ | \ \epsilon (Generates a^n b^n)
B → cBd \ | \ \epsilon (Generates c^m d^m)

By Pumping Lemma: Assume L is regular with pumping length p.
Choose w = 0^p 1^p. Let w = xyz, where |xy| \le p and |y| > 0.
Since |xy| \le p, y consists entirely of 0s. Let y = 0^k (k > 0).
Pump y twice (i=2): xy^2z = 0^{p+k} 1^p.
Since k > 0, p+k \neq p, so the pumped string does not have an equal number of 0s and 1s, which means it is not in L. This contradicts the Pumping Lemma, hence L is not regular.

Proof by Construction:
Let L_1 be a CFL recognized by a Pushdown Automaton M_1 = (Q_1, \Sigma, \Gamma, \delta_1, q_{01}, Z_0, F_1).
Let L_2 be a RL recognized by a Deterministic Finite Automaton M_2 = (Q_2, \Sigma, \delta_2, q_{02}, F_2).
We can construct a new PDA M' that simulates both M_1 and M_2 simultaneously in parallel (cartesian product construction).
The state space of M' will be Q_1 \times Q_2. M' accepts a string if and only if it reaches a final state in F_1 \times F_2.
Since M_2 has no stack, M' only needs to manage the stack of M_1, meaning M' is a valid PDA. Because a PDA recognizes the intersection, the intersection is Context-Free.

A Reduced Grammar is a Context-Free Grammar that has been optimized by strictly removing three types of useless features in the correct order:

1. ε-productions: (e.g., A → \epsilon)
2. Unit productions: (e.g., A → B)
3. Useless symbols: Symbols that are either non-generating (cannot derive a string of terminals) or non-reachable (cannot be reached from the start symbol).

To prove ambiguity, we must find a string that has two distinct Leftmost Derivations (LMDs) or two distinct Parse Trees.
This specific grammar generates strings with an equal number of 'a's and 'b's. However, due to the branching nature of A → bAA and B → aBB, there are multiple paths to derive strings like `aabb`. Since we can construct two different parse trees for the same string, Yes, this grammar is ambiguous.

An even integer ends with 0, 2, 4, 6, or 8. We also need to handle the fact that multi-digit integers shouldn't start with 0 unless it's just the number "0".

Grammar Rules:
S → 0 \ | \ D \ E
D → N \ D \ | \ \epsilon (D represents any number of digits)
N → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
E → 0 | 2 | 4 | 6 | 8 (Even ending digit)

Syntax: Refers to the structure, rules, and grammar of a language. In automata theory, it defines whether a string of symbols is mathematically well-formed according to a set of production rules (e.g., missing semicolons, unmatched parentheses).
Semantics: Refers to the actual meaning or logic of the string. A sentence can be syntactically correct but semantically meaningless (e.g., dividing an integer by a string).

Production rules define the exact mathematical substitutions that dictate how a language's strings are generated. They map non-terminal variables into combinations of other non-terminals and terminals, establishing the fundamental hierarchy and pattern (such as recursion and branching) that defines the expressive power of the language class (Regular, Context-Free, etc.).

We represent integers in unary format (e.g., 3 is "111"). The input is 1^m 0 1^n, representing m + n separated by a '0'.

Algorithm:
1. Read '1', leave it as '1', move Right.
2. When the separator '0' is found, replace it with '1'.
3. Continue moving Right over all remaining '1's.
4. When a Blank (B) is found, move Left one cell.
5. Replace the final '1' with a Blank (B) and move Left to return to start.
Result: The tape now contains 1^{m+n} with no separator, effectively computing addition.