FORMAL LANGUAGE & AUTOMATA THEORY

Answer

Correct Option: (ii) 3

Explanation

To check divisibility by $3$, we only need the remainder modulo 3 of the number. Whether the input is binary, decimal, or octal does not change the number of remainders.

For modulus $3$, there are exactly $3$ possible remainders:

• $r = 0$ → number divisible by 3 (accepting state)
• $r = 1$ → remainder 1
• $r = 2$ → remainder 2

DFA Construction for Octal Alphabet

• Alphabet: $\Sigma = \{0,1,2,3,4,5,6,7\}$
• States: $q_0, q_1, q_2$ representing remainder $0,1,2$
• Start state: $q_0$ (value 0)
• Accepting state: $q_0$
• Transition: On reading octal digit $d$ from state $q_r$,
  $$\delta(q_r, d) = q_{(r \times 8 + d) \bmod 3}$$
  Since $8 \equiv 2 \pmod 3$, this simplifies to $q_{(2r + d) \bmod 3}$.

This DFA is complete and minimal – each remainder is distinguishable (Myhill-Nerode equivalence).

Why other options are wrong

• (i) 1 state: would accept all or no strings, cannot distinguish remainders.
• (iii) 5 and (iv) 7: unnecessary extra states; $\lceil \log_2 3 \rceil$ is not relevant.

Final Answer

Minimum number of states = 3 (one per residue class mod 3).

Answer

Correct Option: (iv) Strings with even number of $0$’s

Explanation

(iv) Even number of $0$’s — Regular

Language $L_4 = \{ w \in \{0,1\}^* \mid \#_0(w) \text{ is even} \}$ is regular. DFA with 2 states suffices:

• $q_0$: even count (start, accepting)
• $q_1$: odd count
  $\delta(q_0,0)=q_1,\;\delta(q_1,0)=q_0,\;\delta(q,1)=q$.

Regular expression: $(1^*0\,1^*0)^*1^*$ or $(1^*01^*01^*)^*$.

By Myhill-Nerode, only 2 equivalence classes.

(i) Length is prime — Not regular

$L_1 = \{ w \mid |w| \in \text{PRIMES} \}$. Use Pumping Lemma. Let $p$ be pumping length, choose $w = 0^p$ where $p$ prime, pump gives length $p + k|y|$ which will be composite for suitable $k$ (e.g., $k=p$). So not regular. Primes set not ultimately periodic.

(ii) Palindromes — Not regular

$L_2 = \{ ww^r \mid w\in\Sigma^*\}^{? }$ Classic non-regular. Requires unbounded stack to compare second half with first reversed. Pumping lemma: $w = 0^p1\,0^p$ in palindrome form fails. Needs PDA, is CFL but not regular.

(iii) Contains $ww^r$ as substring — also Not regular

$L_3 = \{ x \, ww^r \, y \mid \dots\}$ Need to remember arbitrarily long $w$ to check $w^r$ follows. This is not regular (can be shown via Myhill-Nerode with infinitely many distinct suffixes). It is context-sensitive.

Final Answer

Only (iv) is regular.

Answer

Correct Option: (i) $m \le 2^{n}$

Explanation

NFA → DFA subset construction:

• Each DFA state corresponds to a subset of NFA states.
• With $n$ NFA states, there are at most $2^{n}$ subsets.
• Hence the DFA obtained (before minimization) has $\le 2^{n}$ states.
• Minimized DFA $M$ has $m \le$ number of subset-construction DFA states $\le 2^{n}$.

So (i) is always true.

Other options:

• (ii) $n \le m$ is false: NFA can be exponentially smaller (e.g., language of $n^{th}$ from end needs $n+1$ NFA states but $2^{n}$ DFA states → $n < m$ sometimes, but not necessarily; sometimes DFA is smaller).
• The converse $m \ge n$ is not guaranteed.

Final Answer

$m \le 2^{n}$ → Option (i). (Minimized DFA minimal, so $m$ is even tighter, but certainly $\le 2^{n}$.)

Answer

Correct Option: (i) $|Input|+1$

Explanation

Moore Machine: Output depends only on present state, and output is associated with state entry, including the initial state before any input is consumed.

• For input length $n$, the machine visits $n+1$ states: $q_0$ (initial, no input) $\xrightarrow{a_1} q_1 \xrightarrow{a_2} \dots \xrightarrow{a_n} q_n$.
• Each state produces one output symbol $\lambda(q_i)$.
• Hence output string length = $n+1$.

Mealy Machine contrast: Output depends on transition (state + input), so output length = $|Input|$ = $n$ (one per input symbol).

Given input 101010, $|Input|=6$ → Moore output length = $7$.

Final Answer

Moore machine output length is $|Input|+1$ → Option (i).

Answer

Correct Option: (iv) Type-3

Explanation

Chomsky Hierarchy (Noam Chomsky, 1956)

Type	Language Class	Grammar	Automaton
Type-0	Recursively Enumerable	Unrestricted	Turing Machine
Type-1	Context-Sensitive	Context-Sensitive	Linear Bounded Automaton
Type-2	Context-Free	Context-Free	Pushdown Automata
Type-3	Regular	Regular (Left/Right-linear)	Finite Automaton (DFA/NFA)

Regular languages are the most restricted class, generated by:

• Right-linear grammars: $A \rightarrow aB \mid a \mid \epsilon$
• Left-linear grammars
• Regular expressions

and recognized by DFA/NFA/ε-NFA.

They are strictly contained:
$$\text{Type-3} \subset \text{Type-2} \subset \text{Type-1} \subset \text{Type-0}$$

Final Answer

Regular languages are Type-3 languages. Correct option (iv).

Answer

Correct Option: (i) 3 states and 6 transitions (for residue mod 3 Moore machine)

Explanation

To produce residue mod 3, need 3 states corresponding to remainders $0,1,2$.

• Alphabet: e.g., binary or unary? For general input, Moore machine that outputs residue after each symbol needs 3 states.
• Transitions: For binary alphabet $\{0,1\}$, from each of 3 states there are 2 outgoing transitions ($0$ and $1$): $3 \times 2 =6$ transitions. Formula: new remainder $r' = (r \times base + digit) \bmod 3$.

If alphabet were $\{0\}$ unary, transitions =3; but typical exam assumes binary/decimal digit input, hence 6.

Other options (3,5), (2,4) insufficient to represent 3 residues.

Final Answer

3 states, 6 transitions → Option (i). If input alphabet size $|\Sigma|=k$, transitions $=3k$.

Answer

Correct Option: (i) $\{a^n b^n \mid n \ge 0\}$

Explanation

• (ii) $\{a,b\}^*$ → Regular, regex $(a+b)^*$, DFA with 1 state.
• (iii) Finite languages → Regular: any finite set is regular (union of finitely many strings).
• (iv) Languages accepted by DFA → Definition of regular.
• (i) $\{a^n b^n\}$ → Classic non-regular. Requires counting unbounded $n$ and matching $a$'s with $b$'s. Pumping Lemma: let $p$ be pumping length, $w = a^p b^p$, pumping $y$ (all $a$'s) breaks equality $|w|_a = |w|_b$.

It is Context-Free (PDA can push $a$'s, pop for $b$'s) but not regular.

Final Answer

NOT regular is $\{a^n b^n\}$ → Option (i).

Answer

Correct Option: (i) 15 states (Other options typically include 8, etc., correct is 15)

Explanation

Language $L = \{ w \in \{0,1\}^* \mid \#_0(w) \bmod 3 =0 \;\land\; \#_1(w) \bmod 5 =0 \}$.

This is intersection of two regular languages:

• $L_0 = \{ w \mid \#_0(w) \equiv 0 \pmod 3 \}$ → DFA with 3 states ($r_0=0,1,2$).
• $L_1 = \{ w \mid \#_1(w) \equiv 0 \pmod 5 \}$ → DFA with 5 states ($s_0=0..4$).

Intersection via product construction: states = $Q_0 \times Q_1$ → $3 \times 5 =15$ states.

Transitions: $\delta((r,s),0) = ((r+1)\bmod 3, s)$, $\delta((r,s),1) = (r, (s+1)\bmod5)$.

Initial $(0,0)$, accepting $(0,0)$ only. Minimal because all pairs distinguishable (Myhill-Nerode: $(i,j)
ot\equiv (i',j')$if$i
eq i'$or$j
eq j'$).

Final Answer

15 states (product DFA, minimal).

Answer

Correct Option: (ii) The choice of path is nondeterministic (and equivalently (iii); if “All of the mentioned” is offered, (iv) is also defensible)

Explanation

Deterministic FA: $\delta: Q \times \Sigma \rightarrow Q$ — exactly one next state for each $(q,a)$.

Nondeterministic FA: $\delta: Q \times \Sigma \rightarrow 2^{Q}$ — a set of possible next states. The machine may:

• be in several states simultaneously (subset view), or
• guess a path.

So “non-deterministic” means:

• Next state is not uniquely determined → (iii)
• Choice of computation path is nondeterministic → (ii)

The “result” (accept/reject) is determined (exists some accepting path ⇔ accept), so (i) “result undetermined” is misleading.

In many textbooks the canonical answer is (ii) Choice of path is nondeterministic (or (iii)). If option (iv) “All of the mentioned” lumps (ii)+(iii), some keys mark (iv) as correct.

Formal

$N = (Q,\Sigma,\delta,q_0,F)$, $\delta(q,a) = \{p_1,p_2,\dots\}$. On input $w$, $N$ accepts iff there exists a path $q_0 \xrightarrow{w} f\in F$.

Final Answer

NFA is nondeterministic because the next state / path is not uniquely determined → Option (ii) (and (iii)).

Answer

Correct Option: (iv) Output tape (is NOT a component)

Explanation

Finite Automaton (DFA/NFA) formal definition: $M = (Q, \Sigma, \delta, q_0, F)$

Components:

1. $Q$: Finite set of states
2. $\Sigma$: Input alphabet
3. $\delta$: Transition function $Q\times\Sigma \rightarrow Q$ (or $2^Q$ for NFA)
4. $q_0 \in Q$: Start state
5. $F \subseteq Q$: Set of accepting states

Output tape belongs to Turing Machine or Transducer (Mealy/Moore), not to basic finite automaton. FA has no output tape; it only accepts/rejects.

Note: $\epsilon$ and stack are for PDA, tape for TM.

Final Answer

Output tape is not a component of FA → Option (iv).

Answer

Correct Option: (i) Moore machine has no accepting states (in transducer sense; strictly all (i)-(iii) as stated are inaccurate, so if “None of the above” were an option it would be correct — see note)

Explanation

Moore vs Mealy as Transducers

• Moore: Output $\lambda: Q \rightarrow \Gamma$ (state output). Mealy: $\lambda: Q \times \Sigma \rightarrow \Gamma$ (transition output).
• In classical transducer definition (Hopcroft-Ullman), they are not acceptors — they have no $F$ set. They translate every input to an output, not accept/reject. In that sense (i) “Moore has no accepting states” is true for the pure transducer, and similarly Mealy also has none, making (ii) false.

Convertibility

• Mealy ↔ Moore are interconvertible:
  • Mealy → Moore: expand states (at most $|Q|\cdot|\Gamma|$), output delayed by one symbol.
  • Moore → Mealy: keep same states, shift output to transitions.
  • So (iii) “Mealy to Moore but not vice versa” is false. Both directions possible.

Evaluation

Statement	Truth
(i) Moore has no accepting states (pure transducer)	True
(ii) Mealy has accepting states	False (pure Mealy also has none)
(iii) Mealy→Moore only one way	False
(iv) All of above	False

If the question is asked in the acceptor + transducer mixed sense where Moore/Mealy can be defined with $F$, then (i) and (ii) are both false and no option is strictly correct; the intended exam key is usually (i).

Final Answer

Per standard syllabus, (i) is the expected correct choice. Rigorously, pure Moore/Mealy are transducers without $F$, and they are mutually convertible.

Answer

Correct Option: (iii) $2^{n}$

Explanation

NFA with $n$ states → DFA via subset construction:

Each DFA state is a subset of NFA states. NFA states set $Q_N$, $|Q_N|=n$.

Number of distinct subsets = $|\mathcal{P}(Q_N)| = 2^{n}$.

This includes $\emptyset$ (dead state).

Hence DFA has at most $2^{n}$ states. Upper bound is tight: there exist NFA families (e.g., language “$n$th symbol from end is 1”) that require exactly $2^{n}$ DFA states.

Final Answer

Maximum $2^{n}$ states → Option (iii). (Minimal DFA may be smaller, but maximum is $2^{n}$.)

Answer

Correct Option: (ii) Multiple accepting states

Explanation

DFA definition: $M = (Q,\Sigma,\delta,q_0,F)$

• $q_0$: Exactly one start state → (i) multiple start states false. (NFA can have multiple, DFA has one).
• $F \subseteq Q$: Set of final/accepting states. Can be 0, 1, or multiple → (ii) true. Example even number of 0's DFA has 1 accept, but language $(a+b)^*ab$ needs 1, language “ends with 00 or 11” needs 2.
• Transitions: $\delta: Q \times \Sigma \rightarrow Q$ is total deterministic, no $\epsilon$-moves. $\epsilon$-transitions allowed only in $\epsilon$-NFA → (iii) false.

Final Answer

DFA can have multiple accepting states → Option (ii).

Answer

Correct Option: (i) 4

Explanation

Regular expression: $\{a,b\}^* baaa$ — language is all strings over $\{a,b\}$ ending with suffix baaa.

To accept, a DFA must detect suffix b a a a (length 4).

Minimal DFA (suffix automaton)

States represent longest suffix of processed prefix that is prefix of baaa:

• $q_0$: no part matched (or last $b$ irrelevant)
• $q_1$: suffix b
• $q_2$: suffix ba
• $q_3$: suffix baa
• $q_4$: suffix baaa (accepting)

Transitions: each new character extends/collapses the match. From $q_0$, on b → $q_1$, on a → $q_0$; etc.

Number of transitions on the shortest path from start $q_0$ to final $q_4$ is 4 (b→a→a→a).

Number of states =5, transitions to reach final =4. Some keys count states=5 as “transitions”, but minimum edge traversals is 4.

Final Answer

4 transitions (5 states) to reach final — Option (i) 4. If counting states, answer is 5.

Answer

Correct Option: (iv) $\{00 + (11)^*0\}^*$

Explanation

Test $w=1101$ against each regex:

(i) $1^*0^*(0+1)$: = $1^*$ then $0^*$ then single $0$ or $1$. $1101 = \underbrace{11}_{1^*} \underbrace{0}_{0^*} \underbrace{1}_{(0+1)}$ → belongs.

(ii) $1(0+1)^*101$: Must start with $1$ and end with $101$. $1101 = 1 \underbrace{1}_{(0+1)^*}101$? Actually $1101$ = $1$ + $\epsilon$ + $101$ with middle $1$? $1(0+1)^*101 = 1\,x\,101$ where $x=0$? For $w=1101$, $x=0$? Wait $1+0+101 =1101$ exactly, so $w = 1\cdot0\cdot101$? No $1\cdot101 =1101$ with $x=\epsilon$? $1(0+1)^* =1$, remaining $101 =101$ → $1101$ → belongs.

(iii) $(1(0)^*(0+1)^*(0+1))^*$: This is essentially $\Sigma^*$ variant (can generate any string) → belongs.

(iv) $\{00 + (11)^*0\}^*$: Generators: $00$ (ends 0) and $(11)^*0$ = even 1's followed by 0, also ends 0. Any concatenation of blocks ending in 0 always ends in 0. $1101$ ends in 1 → does not belong.

Final Answer

$1101
otin {00 + (11)^0}^$ → Option (iv).

Answer

Correct Option: (ii) Pumping

Explanation

Pumping Lemma concept: For regular/CFL languages, any long string $w = xyz$ (with $|y|>0$, $|xy|\le p$) can be pumped: $xy^i z \in L$ for all $i \ge 0$ (repeating $y$ zero, one, or more times).

• Pumping = repeating the middle portion $y$ zero or more times and checking membership.
• Generating is general derivation.
• Producing is vague.

The lemma is used to prove non-regularity/non-CFL by contradiction.

Final Answer

Repeating $y$ is Pumping → Option (ii).

Answer

Correct Option: (iv) All of the above

Explanation

Chomsky Hierarchy classifies grammars into 4 types:

Type	Name	Production Form	Language Class
Type-0	Unrestricted	$\alpha \rightarrow \beta$, no restriction	Recursively Enumerable (TM)
Type-1	Context-Sensitive	$|\alpha| \le |\beta|$, $\alpha \rightarrow \beta$ with context	CSL (LBA)
Type-2	Context-Free	$A \rightarrow \gamma$, $A\in V$	CFL (PDA)
Type-3	Regular	$A \rightarrow aB \mid a$, $A\rightarrow a$	Regular (FA)

• (i) Regular → Type-3 ✓
• (ii) Context-Free → Type-2 ✓
• (iii) Context-Sensitive → Type-1 ✓

All three are in Chomsky hierarchy (Type-0 is the super-set).

Final Answer

All are types → Option (iv) All of the above.

Answer

Correct Option: (i) $m \le 2^{n}$

Explanation

Same as Q28 / Q87: Subset construction.

NFA $n$ states → DFA has at most $2^{n}$ subsets. Minimized DFA $m$ ≤ subset DFA ≤ $2^{n}$.

• (ii) $n \le m$ is not necessarily true (NFA can be smaller).
• (iv) $m =2^{n}$ is not always (upper bound, but often smaller).
• (iii) one accept state is false (can be multiple).

Final Answer

$m \le 2^{n}$ → Option (i).

Answer

Correct Option: (iii) All finite strings over $\Sigma$ including $\epsilon$

Explanation

Definition: $\Sigma^* = \bigcup_{i=0}^{\infty} \Sigma^i$, where $\Sigma^0 = \{\epsilon\}$, $\Sigma^1 = \Sigma$, $\Sigma^2 = \Sigma\Sigma$, ...

For $\Sigma = \{a,b\}$:

• $\epsilon$ (empty string, length 0) ∈ $\Sigma^*$
• $a, b$ ∈ $\Sigma^*$
• $aa, ab, ba, bb$ ∈ $\Sigma^*$
• … all finite concatenations.

Properties:

• Countably infinite set.
• Does not contain infinite strings (each string is finite; there are infinitely many strings, but each has finite length).
• Not limited to equal length.

Options:

• (i) Only finite strings but missing $\epsilon$ → incomplete
• (ii) Only infinite strings → false
• (iv) Only equal length → false

Final Answer

All finite strings including $\epsilon$ → Option (iii).

Answer

Correct Option: (i) The set of states reachable using $\epsilon$ only

Explanation

$\epsilon$-closure $\text{ECLOSE}(q)$ for NFA-$\epsilon$:

$\text{ECLOSE}(q) = \{ p \mid q \xrightarrow{\epsilon^*} p \}$ — all states reachable from $q$ by zero or more $\epsilon$-moves, including $q$ itself.

Example: $q_0 \xrightarrow{\epsilon} q_1 \xrightarrow{\epsilon} q_2$ → ECLOSE($q_0$) = $\{q_0,q_1,q_2\}$.

Used in subset construction for $\epsilon$-NFA → DFA/NFA conversion: $\delta_D(S,a) = \text{ECLOSE}(\bigcup_{q\in S} \delta(q,a))$.

Other options are incorrect: not unreachable, not just finals, not dead states.

Final Answer

$\epsilon$-closure = states via $\epsilon$ only → Option (i).

Answer

Correct Option: (i) 15 states

Explanation

Language $L = \{ w \mid \#_0 \bmod 3 =0,\; \#_1 \bmod 5 =0\}$ is same as Q92 / Q112.

As before: DFA for $\#_0 \bmod 3$ needs 3 states, for $\#_1 \bmod 5$ needs 5 states. Product → $3 \times 5 =15$ minimal states.

Transitions: $15 \times 2 =30$.

Other options 11,10,9 would be for different moduli (e.g., 3+5=8) — incorrect; must multiply, not add.

Final Answer

15 states → Option (i).

Answer

Correct Option: (iv) $\{ w \mid w \text{ starts with 'a' and ends with 'b'} \}$

Explanation

Test each:

• (i) $\{a^n b^n\}$ → Not regular (needs stack, CFL).
• (ii) Equal number of $a$'s and $b$'s → $\{ w \mid \#_a = \#_b \}$ not regular (needs counting). Pumping fails.
• (iii) $\{a^n \mid n \text{ prime}\}$ → Not regular (non-periodic), also not CFL.
• (iv) Starts with a and ends with b → Regular.

DFA for (iv): 3 states

• $q_0$ start (no symbol yet, non-accepting)
• $q_1$ = last symbol a? Actually needs start a, so $q_0 \xrightarrow{a} q_1$, $q_0 \xrightarrow{b} q_{dead}$.
• $q_1$ = seen start a, last is a (non-accepting)
• $q_2$ = seen start a, last is b (accepting)
  Transitions: $q_1 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_2$, $q_2 \xrightarrow{a} q_1$, $q_2 \xrightarrow{b} q_2$.

Regular expression: $a(a+b)^*b$ (plus handle length 1? Actually $ab$ inclusive). More precisely $a\Sigma^*b$.

Hence regular.

Final Answer

Only (iv) is regular.

Answer

Correct Option: (iii) $R = QP^*$ (Arden’s Theorem)

Explanation

Arden’s Theorem: If $P$ does not contain $\epsilon$, then equation $R = Q + RP$ has unique solution $R = QP^*$.

Proof: $R = Q + (Q + RP)P = Q(\epsilon + P) + RP^2 = \dots = Q(\epsilon + P + P^2 + \dots + P^{k}) + RP^{k+1}$. As $k \to \infty$, $RP^{k+1}$ contributes no finite strings if language, so $R = QP^*$.

• (i) $QP$ missing star → incomplete.
• (ii) $PQ^*$ swaps order (concatenation not commutative).
• (iv) duplicate of (iii).

Condition: $P$ not null ($\epsilon
otin P$) ensures uniqueness.

Final Answer

$R = QP^*$ → Option (iii) (also (iv) if duplicate).

Answer

Correct Option: (ii) $O(2^{m})$

Explanation

NFA with $m$ states → DFA via subset construction:

Number of DFA states $= 2^{m}$ in worst case, and constructing each state requires processing transitions for each symbol ($|\Sigma|$).

Time is proportional to number of subsets times alphabet:

$$T = O(|\Sigma| \cdot 2^{m}) = O(2^{m})$$

(If counting edges, $O(m \cdot 2^{m})$ but dominant exponential.)

Options:

• $O(m^2)$ — polynomial, false for NFA→DFA
• $O(m)$ — linear, false
• $O(\log m)$ — false

Final Answer

$O(2^{m})$ → Option (ii).

Answer

Chomsky Hierarchy of Grammars

Type	Grammar Name	Production Form $\alpha \rightarrow \beta$	Language Class	Automaton
Type-0	Unrestricted	No restriction on $\alpha,\beta$ (except $\alpha
eq \epsilon$)	Recursively Enumerable (RE)	Turing Machine
Type-1	Context-Sensitive	$|\alpha| \le |\beta|$, $\beta$ has $\alpha$ in context	Context-Sensitive (CSL)	Linear Bounded Automaton
Type-2	Context-Free	$A \rightarrow \gamma$, $A \in V$, $\gamma \in (V \cup T)^*$	Context-Free (CFL)	Pushdown Automaton (PDA)
Type-3	Regular / Right-Linear	$A \rightarrow aB \mid a$ (or left-linear)	Regular (REG)	Finite Automaton (DFA/NFA)

Examples

Type	Example Grammar	Language Generated
Type-0	$S \rightarrow aSb \mid \epsilon$ with unrestricted rules e.g. $aB \rightarrow Ba$	$\{a^n b^n c^n \mid n\ge0\}$ or any computable language
Type-1	$S \rightarrow aBC \mid aSBC$, $CB \rightarrow BC$, $aB \rightarrow ab$, $bB \rightarrow bb$, $bC \rightarrow bc$, $cC \rightarrow cc$	$\{a^n b^n c^n \mid n\ge1\}$
Type-2	$S \rightarrow aSb \mid SS \mid \epsilon$	$\{w \mid \#_a(w) = \#_b(w)\}$ (balanced parentheses)
Type-2	$S \rightarrow (S) \mid SS \mid \epsilon$	Balanced parentheses language
Type-3	$S \rightarrow 0S \mid 1S \mid \epsilon$	$\{0,1\}^*$ (all binary strings)
Type-3	$S \rightarrow aS \mid bA$, $A \rightarrow bA \mid b$	$\{a^m b^n \mid m,n\ge1\}$ (right-linear)

Containment Relations

$$\text{REG} \subset \text{DCFL} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} \subset \text{ALL}$$

Each level strictly contained in the next (proper subsets).

Notes

• Type-0 = RE = recognized by TM; not all decidable.
• Type-1 = CSL = decided by LBA (PSPACE-complete membership).
• Type-2 = CFL = parsed in $O(n^3)$ (CYK); inherently ambiguous CFLs exist.
• Type-3 = REG = recognized by FA/DFA; all decidable properties.

Final Answer

Table above summarizes all four Chomsky types with production forms, language classes, automata, and concrete grammar examples.