2024 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

26 questions

Q1a. If an infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is: (i) Compiler (ii) Interpreter (iii) Loader and Linkers (iv) None of the mentioned20242m
Module 4: Turing Machines (TM)
If an infinite language is passed to Machine $M$ , the subsidiary which gives a finite solution to the infinite input tape is:

(i) Compiler
(ii) Interpreter
(iii) Loader and Linkers
(iv) None of the mentioned

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer

Correct Option: (iv) None of the mentioned

Explanation

An infinite language requires a machine with unbounded memory. In the Turing Machine model $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ the tape is infinite, but the finite control itself is finite.

Compiler: Translates a high-level program to target code before execution. It does not provide run-time handling of an infinite input tape; it assumes input is finite source text.

Interpreter: Executes source line-by-line, still requires entire input to be presented finitely; it does not make an infinite tape finite.

Loader and Linkers: Perform loading / relocation of object code into memory. They handle finite modules, not an infinite language / infinite tape.

The subsidiary that actually gives a finite description of an infinite computation is the finite control (finite automaton) + the Turing Machine’s transition function or, in language theory, the finite representation (regular expression / grammar / TM description) itself. None of the three listed system softwares fulfills this role.

The theoretical concept is:

Infinite language $L \subseteq \Sigma^*$ is described finitely by a grammar / regular expression / TM encoding $\langle M \rangle$ , not by compiler/interpreter/loader.

Hence none of (i)-(iii) is correct.

Final Answer

None of the mentioned. The finite solution is provided by the finite control / finite encoding $\langle M\rangle$ of the machine, not by compiler / interpreter / loader.
Q1b. Which of the following is a regular language? (i) Strings whose length is a sequence of prime numbers (ii) Palindrome strings (iii) Strings containing substring ww^r (iv) Strings with even number of 0’s20242m
Module 1: Introduction & Regular Languages
Which of the following is a regular language?

(i) Strings whose length is a sequence of prime numbers
(ii) Palindrome strings
(iii) Strings containing substring $ww^r$
(iv) Strings with even number of $0$ ’s

View this question on its own page →
Search Google Ask AI
Worked Solution
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.
Q1c. NFA has 'non-deterministic' in its name because: (i) The result is undetermined (ii) The choice of path is nondeterministic (iii) The next state is nondeterministic (iv) All of the mentioned20242m
Module 1: Introduction & Regular Languages
NFA has 'non-deterministic' in its name because:

(i) The result is undetermined
(ii) The choice of path is nondeterministic
(iii) The next state is nondeterministic
(iv) All of the mentioned

View this question on its own page →
Search Google Ask AI
Worked Solution
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)).
Q1d. Which of the following is NOT a component of a finite automaton? (i) States (ii) Input alphabet (iii) Transition function (iv) Output tape20242m
Module 1: Introduction & Regular Languages
Which of the following is NOT a component of a finite automaton?

(i) States
(ii) Input alphabet
(iii) Transition function
(iv) Output tape

View this question on its own page →
Search Google Ask AI
Worked Solution
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:

$Q$ : Finite set of states

$\Sigma$ : Input alphabet

$\delta$ : Transition function $Q\times\Sigma \rightarrow Q$ (or $2^Q$ for NFA)

$q_0 \in Q$ : Start state

$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).
Q1e. A DFA can have: (i) Multiple start states (ii) Multiple accepting states (iii) Transitions on \varepsilon (iv) None of the above20242m
Module 1: Introduction & Regular Languages
A DFA can have:

(i) Multiple start states
(ii) Multiple accepting states
(iii) Transitions on $\varepsilon$
(iv) None of the above

View this question on its own page →
Search Google Ask AI
Worked Solution
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).

Q1f. Which of the following is a type of grammar in the Chomsky hierarchy? (i) Regular (ii) Context-Free (iii) Context-Sensitive (iv) All of the above20242m

Module 1: Introduction & Regular Languages

Which of the following is a type of grammar in the Chomsky hierarchy?

(i) Regular
(ii) Context-Free
(iii) Context-Sensitive
(iv) All of the above

View this question on its own page →

Search Google Ask AI

Worked Solution

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.

Q1g. A Turing Machine has: (i) A finite tape (ii) An infinite tape (iii) A stack (iv) A queue20242m
Module 4: Turing Machines (TM)
A Turing Machine has:

(i) A finite tape
(ii) An infinite tape
(iii) A stack
(iv) A queue

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer

Correct Option: (ii) An infinite tape

Explanation

Turing Machine model: $M = (Q,\Sigma,\Gamma,\delta,q_0,B,F)$ with

Finite control (states $Q$ ),

One infinite tape divided into cells, each holds symbol from $\Gamma$ ( $\Sigma \subset \Gamma$ ), extends infinitely in one direction (or both in some definitions), with a read/write head.

Initially tape contains input $w$ + blanks $B$ to the right (infinite blanks).

It does not have a stack (that's PDA) or queue as primary memory, nor finite tape (that would be LBA / finite automaton).

Final Answer

TM has an infinite tape → Option (ii).

Q1h. Which of the following problems is undecidable? (i) DFA acceptance (ii) NFA acceptance (iii) The Halting Problem (iv) Regular expression matching20242m

Module 5: Undecidability

Which of the following problems is undecidable?

(i) DFA acceptance
(ii) NFA acceptance
(iii) The Halting Problem
(iv) Regular expression matching

View this question on its own page →

Search Google Ask AI

Worked Solution

Answer

Correct Option: (iii) The Halting Problem

Explanation

Decidability:

Problem	Decidable?
DFA acceptance $w \in L(DFA)$ ?	Decidable — simulate DFA $O(\|w\|)$
NFA acceptance	Decidable — subset simulation or convert to DFA
Regex matching $w \in L(R)$ ?	Decidable — convert to DFA/NFA
Emptiness $L(DFA)=\emptyset$ ?	Decidable
Halting Problem $M$ halts on $w$ ?	Undecidable (Turing 1936)

Proof sketch: Assume $H(\langle M,w\rangle)$ decides halting, diagonalize with $D(\langle M\rangle)=$ loop if $M$ halts on $\langle M\rangle$ else halt. $D(\langle D\rangle)$ contradicts.

Final Answer

Undecidable is Halting Problem → Option (iii).

Q1i. Which of these represents a regular language? (i) \{ a^n b^n \mid n \ge 0 \} (ii) Strings with equal number of a’s and b’s (iii) \{ a^n \mid n \text{ is prime} \} (iv) \{ w \mid w \text{ starts with 'a' and ends with 'b'} \}20242m
Module 1: Introduction & Regular Languages
Which of these represents a regular language?

(i) $\{ a^n b^n \mid n \ge 0 \}$
(ii) Strings with equal number of $a$ ’s and $b$ ’s
(iii) $\{ a^n \mid n \text{ is prime} \}$
(iv) $\{ w \mid w \text{ starts with 'a' and ends with 'b'} \}$

View this question on its own page →
Search Google Ask AI
Worked Solution
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.
Q1j. Which of the following is a PDA? (i) Finite automaton with a stack (ii) Turing machine with a stack (iii) Finite automaton with a queue (iv) Turing machine with a queue20242m
Module 2: Context-Free Languages (CFL) and PDA
Which of the following is a PDA?

(i) Finite automaton with a stack
(ii) Turing machine with a stack
(iii) Finite automaton with a queue
(iv) Turing machine with a queue

View this question on its own page →
Search Google Ask AI
Worked Solution
Answer

Correct Option: (i) Finite automaton with a stack

Explanation

PDA definition: $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$

Essentially a finite automaton (finite control) augmented with a stack (LIFO memory).

Stack provides unbounded memory but restricted access (push/pop at top only).

Enables recognition of CFLs: e.g., $\{a^n b^n\}$ by pushing $a$ 's, popping for $b$ 's.

Options:

(ii) TM with stack → equivalent to TM (stack is not needed)

(iii) FA with queue → queue automaton = TM-powerful

PDA = FA + stack.

Final Answer

PDA = FA + stack → Option (i).
Budget App•POCKETLY
Pocketly on Android
Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.
Install Pocketly

Q2a. What is Automata? Explain classification of Automata.20247m

Module 1: Introduction & Regular Languages

What is Automata? Explain classification of Automata.

View this question on its own page →

Search Google Ask AI

Worked Solution

Answer

1. What is Automata?

Automata (plural of Automaton) is an abstract mathematical model of computation. It is a finite representation of an infinite computation that reads input symbols, changes states according to transition rules, and decides acceptance. It is the theoretical foundation for compiler design, lexical analysis, and computability.

Formally, automaton = (Input + Finite Control + Memory + Output/Acceptance).

No physical infinite hardware is needed; the model studies what can be computed with given memory.

2. Classification of Automata

Classification follows memory power and matches Chomsky hierarchy:

MermaidDiagram

Rendering diagram…

A. Finite Automata (FA) — Type-3, Regular

Memory: Only finite control ( $Q$ ), no auxiliary memory.
Types: DFA ( $\delta: Q\times\Sigma\rightarrow Q$ ), NFA, $\epsilon$ -NFA (all equivalent).
Power: Regular languages. Example: $L = \{ w \mid \#_0(w) \text{ even}\}$ , $(a+b)^*ab$ .
Use: Lexical analyzer, pattern matching.

B. Pushdown Automata (PDA) — Type-2, Context-Free

Memory: Stack (LIFO). $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ .
Types: DPDA vs NPDA (different power).
Power: CFLs. Example: $L = \{a^n b^n \mid n\ge0\}$ , balanced parentheses, arithmetic expressions.
Use: Syntax analysis (parsing).

C. Linear Bounded Automaton (LBA) — Type-1, Context-Sensitive

Memory: Tape bounded by input length $|w|$ (plus two endmarkers). Can read/write but not beyond bounds.
Power: CSLs. Example: $L = \{a^n b^n c^n\}$ , $\{a^{n^2}\}$ .
Use: Rare in practice, studies context-sensitive features.

D. Turing Machine (TM) — Type-0, RE

Memory: Infinite tape, read/write head, finite control.
Types: Deterministic, Nondeterministic, Multi-tape, Universal (all equivalent in power).
Power: Recursively Enumerable (Type-0) and Recursive (Decidable) with always-halting variant.
Example: $L = \{ ww \mid w\in\{a,b\}^*\}$ , Halting, any computable function.
Use: Model of general-purpose computer.

Summary Table

Automaton	Memory	Grammar Type	Language	Decidability
FA (DFA/NFA)	$Q$	Type-3 Regular	Regular	Decidable (all properties)
PDA	$Q$ + Stack	Type-2 CFG	CFL	Emptiness decidable, equivalence undecidable
LBA	$Q$ + tape $\|w\|$	Type-1 CSG	CSL	Membership decidable ( $PSPACE$ )
TM	$Q$ + $\infty$ tape	Type-0 unrestricted	RE	Halting undecidable

Hierarchy: $\text{FA} \subset \text{PDA} \subset \text{LBA} \subset \text{TM}$ and $\text{Regular} \subset \text{CFL} \subset \text{CSL} \subset \text{RE}$ .

Final Answer

Automata are abstract computing models; classification by memory gives FA → PDA → LBA → TM corresponding to Chomsky Types 3→2→1→0.

Q2b. Tabulate the Chomsky hierarchy of grammars with an example of each.20247m
Module 1: Introduction & Regular Languages
Tabulate the Chomsky hierarchy of grammars with an example of each.

View this question on its own page →
Search Google Ask AI

Q3a. Construct DFA for all strings over \{0,1\} interpreted as binary numbers divisible by 4.20247m

Module 1: Introduction & Regular Languages

Construct DFA for all strings over $\{0,1\}$ interpreted as binary numbers divisible by $4$ .

View this question on its own page →

Search Google Ask AI

Worked Solution

Answer

Language: $L = \{ w \in \{0,1\}^* \mid \text{value}_2(w) \equiv 0 \pmod 4 \}$

Interpret string as binary number (most significant bit first), check divisibility by 4.

Key Observation

A binary number is divisible by 4 iff its last two bits are 00 (or the string is just "0" or empty, treated as 0).

Binary $x \equiv 0 \pmod 4 \iff x$ ends in 00.
Special case: empty string $\epsilon$ and "0" represent 0, divisible by 4.

DFA Construction (4 states)

Track value modulo 4. States = residues $\{0,1,2,3\}$ .

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

$Q = \{q_0, q_1, q_2, q_3\}$ where $q_r$ = value $\equiv r \pmod 4$
$\Sigma = \{0,1\}$
$q_0$ = start (value 0)
$F = \{q_0\}$ (residue 0)

Transition: On input bit $b \in \{0,1\}$ :

\delta(q_r, b) = q_{(2r + b) \bmod 4}

Transition Table:

State \ Input	0	1
$q_0$ (0)	$q_0$	$q_1$
$q_1$ (1)	$q_2$	$q_3$
$q_2$ (2)	$q_0$	$q_1$
$q_3$ (3)	$q_2$	$q_3$

Derivation:

$2 \times 0 + 0 = 0 \to q_0$
$2 \times 0 + 1 = 1 \to q_1$
$2 \times 1 + 0 = 2 \to q_2$
$2 \times 1 + 1 = 3 \to q_3$
$2 \times 2 + 0 = 4 \equiv 0 \to q_0$
$2 \times 2 + 1 = 5 \equiv 1 \to q_1$
$2 \times 3 + 0 = 6 \equiv 2 \to q_2$
$2 \times 3 + 1 = 7 \equiv 3 \to q_3$

State Diagram

MermaidDiagram

Rendering diagram…

Simplified 3-State DFA (Using Last-Two-Bits Insight)

Since divisibility by 4 depends only on last 2 bits = 00:

DFA with 3 states:

$q_0$ : start, also accept (0 or empty or ...00)
$q_1$ : last bit = 1
$q_2$ : last bit = 0, previous ≠ 0 (i.e., ends in 10)

State \ Input	0	1
$q_0$ (accept)	$q_0$	$q_1$
$q_1$	$q_2$	$q_1$
$q_2$	$q_0$	$q_1$

$F = \{q_0\}$ . $q_0$ = last two bits 00 (or empty/"0").

Why 3 states minimal: Myhill-Nerode: $\epsilon, 1, 10$ are pairwise distinguishable mod 4.

Test Cases

Input	Value	Path	Accept?
$\epsilon$	0	$q_0$	Yes
`0`	0	$q_0 \xrightarrow{0} q_0$	Yes
`100`	4	$q_0 \to q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_0$	Yes
`1000`	8	$q_0 \to q_1 \to q_2 \to q_0 \to q_0$	Yes
`10`	2	$q_0 \to q_1 \xrightarrow{0} q_2$	No ($q_2
otin F$)
`101`	5	$q_0 \to q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_1$	No
`1100`	12	ends in $q_0$	Yes

Regular Expression

$(0+1)^*00 + 0$

(All strings ending in 00 plus the single 0; $\epsilon$ can be included as (0+1)*00 | 0 | \epsilon)

Final Answer

DFA with 4 states (mod 4 tracking) or minimal 3 states:

States: residues 0,1,2,3 (or 3-state: 00, ends-in-1, ends-in-10)
Transitions: $\delta(q_r, b) = q_{(2r+b)\bmod 4}$
Accept: $q_0$ only
Binary divisible by 4 ⇔ ends in 00 (or is 0/ε)

DFA(3 states):
q0 --0--> q0
q0 --1--> q1
q1 --0--> q2
q1 --1--> q1
q2 --0--> q0
q2 --1--> q1
Accept: q0

Q3b. Construct DFA that accepts strings over \Sigma = \{a,b\} which start with aba.20247m
Module 1: Introduction & Regular Languages
Construct DFA that accepts strings over $\Sigma = \{a,b\}$ which start with $aba$ .

View this question on its own page →
Search Google Ask AI
Q4a. Prove that L = \{ a^i b^i \mid i \ge 0 \} is not regular using the pumping lemma.20247m
Module 1: Introduction & Regular Languages
Prove that $L = \{ a^i b^i \mid i \ge 0 \}$ is not regular using the pumping lemma.

View this question on its own page →
Search Google Ask AI
Q4b. Convert the following NFA to DFA. ![NFA](https://res.cloudinary.com/djkpavwmp/image/upload/v1764448480/portfolio_assets/iu08cu9n2cx5gpr1qvv5.png)20247m
Module 1: Introduction & Regular Languages
Convert the following NFA to DFA.

View this question on its own page →
Search Google Ask AI
Q5a. Design a Turing Machine that increments a binary number by 1.20247m
Module 4: Turing Machines (TM)
Design a Turing Machine that increments a binary number by $1$ .

View this question on its own page →
Search Google Ask AI
Q5b. Write the difference between Pushdown Automata and Finite Automata.20247m
Module 2: Context-Free Languages (CFL) and PDA
Write the difference between Pushdown Automata and Finite Automata.

View this question on its own page →
Search Google Ask AI
Q6a. Construct a PDA for the language: L = \{ 0^m 1^n 0^k \mid k \ge 1, m \ge 1, m > n + 2 \}20247m
Module 2: Context-Free Languages (CFL) and PDA
Construct a PDA for the language:

$L = \{ 0^m 1^n 0^k \mid k \ge 1, m \ge 1, m > n + 2 \}$

View this question on its own page →
Search Google Ask AI
Q6b. Explain the various types of Turing Machines.20247m
Module 4: Turing Machines (TM)
Explain the various types of Turing Machines.

View this question on its own page →
Search Google Ask AI
Budget App•POCKETLY
Pocketly on Android
Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.
Install Pocketly
Q7a. Construct a PDA for the grammar: S \to 0BB B \to 0S \mid 1S \mid 0 Test whether 0104 is accepted by this PDA.20247m
Module 2: Context-Free Languages (CFL) and PDA
Construct a PDA for the grammar:

$S \to 0BB$
$B \to 0S \mid 1S \mid 0$

Test whether $0104$ is accepted by this PDA.

View this question on its own page →
Search Google Ask AI
Q7b. Check whether the grammar is ambiguous: S \to a \mid abSb \mid aAb A \to bS \mid aAAb20247m
Module 2: Context-Free Languages (CFL) and PDA
Check whether the grammar is ambiguous:

$S \to a \mid abSb \mid aAb$
$A \to bS \mid aAAb$

View this question on its own page →
Search Google Ask AI
Q8a. Define NFA with \varepsilon-transitions with an example.20247m
Module 1: Introduction & Regular Languages
Define NFA with $\varepsilon$ -transitions with an example.

View this question on its own page →
Search Google Ask AI
Q8b. Prove the pumping lemma for regular languages.20247m
Module 1: Introduction & Regular Languages
Prove the pumping lemma for regular languages.

View this question on its own page →
Search Google Ask AI
Q9a. Write short notes on: 1. Minimization of DFA 2. Type 2 grammar (Context-Free Grammar)20247m
Module 1: Introduction & Regular Languages
Write short notes on:
1. Minimization of DFA
2. Type 2 grammar (Context-Free Grammar)
View this question on its own page →
Search Google Ask AI
Q9b. Write short notes on: 1. Post Correspondence Problem (PCP) 2. NP-hard problem20247m
Module 5: Undecidability
Write short notes on:
1. Post Correspondence Problem (PCP)
2. NP-hard problem
View this question on its own page →
Search Google Ask AI

Previous year2023 Next year2025

Free AppAndroid App

Coursify Android App

Generate AI courses, take quick quizzes between classes, and master complex engineering concepts on the go.

Install Coursify

FORMAL LANGUAGE & AUTOMATA THEORY

Answer

Explanation

Final Answer

Answer

Explanation

(iv) Even number of 000’s — Regular

(i) Length is prime — Not regular

(ii) Palindromes — Not regular

(iii) Contains wwrww^rwwr as substring — also Not regular

Final Answer

Answer

Explanation

Formal

Final Answer

Answer

Explanation

Final Answer

Answer

Explanation

Final Answer

Answer

Explanation

Final Answer

Answer

Explanation

Final Answer

Answer

Explanation

Final Answer

Answer

Explanation

Final Answer

Answer

Explanation

Final Answer

Pocketly on Android

Answer

1. What is Automata?

2. Classification of Automata

A. Finite Automata (FA) — Type-3, Regular

B. Pushdown Automata (PDA) — Type-2, Context-Free

C. Linear Bounded Automaton (LBA) — Type-1, Context-Sensitive

D. Turing Machine (TM) — Type-0, RE

Summary Table

Final Answer

Answer

Key Observation

DFA Construction (4 states)

State Diagram

Simplified 3-State DFA (Using Last-Two-Bits Insight)

Test Cases

Regular Expression

Final Answer

Pocketly on Android

Coursify Android App

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

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