Match the following : Codes : a b c d List – I List – II a. Context free grammar i. Linear bounded automaton b. Regular grammar ii. Pushdown automaton c. Context sensitive grammar iii. Turing machine d. Unrestricted grammar iv. Deterministic finite automaton
ii iv iii i
Each grammar in List – I is paired with one machine model in List – II, using the codes printed under a b c d.
a. Context free grammar → pushdown automaton (ii): the stack lets the machine keep count of nested structure such as \(a^n b^n\), which is exactly what context-free productions generate. So a → ii.
b. Regular grammar → deterministic finite automaton (iv): a regular grammar needs only a finite number of states and no extra memory, which is what a DFA provides. So b → iv.
c. Context sensitive grammar → Turing machine (iii): every context-sensitive language is recursive, so a Turing machine that always halts can decide membership for it. So c → iii.
d. Unrestricted grammar → linear bounded automaton (i): with a, b and c fixed, the remaining machine in List – II, the linear bounded automaton, goes with the unrestricted grammar. So d → i.
The matching is therefore a → ii, b → iv, c → iii, d → i.
Hence, the answer is ii iv iii i.
Similar Questions
Given the recursively enumerable language (\(L_{RE}\)), the context sensitive language (\(L_{CS}\)), the recursive language (\(L_{REC}\)), the context free language (\(L_{CF}\)) and deterministic context free language (\(L_{DCF}\)). The relationship between these families is given by
The family of context sensitive languages is __________ under union and __________ under reversal.
Match the LIST-I with LIST-II
LIST-I LIST-II A. Type - 0 grammar I. Linear Grammar B. Type - 1 grammar II. GNF C. Type - 2 grammar III. x→y, |x|<|y|; x, y ∈ {V ∪ T}* D. Type - 3 grammar IV. Recursively Enumerable Choose the correct answer from the options given below:
Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy :
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted Grammars
Choose the correct answer from the options given below :
Which of the following is ε-free grammar?
Which of the following pairs have different expressive power ?
Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct ?
Important Questions from Automata Theory Concepts - Teaching
- Which of the following is FALSE ?
- Match List I with List II
List I List II A. Type 3 Grammar I. V $\rightarrow$ (V $\cup$$\Sigma$)* B. Type 2 Grammar II. $\lambda$V$\beta$ $\rightarrow$ $\lambda$(V $\cup$$\Sigma$)*$\beta$, where ($\lambda$,$\beta$)$\epsilon$(V $\cup$$\Sigma$)* C. Type 1 Grammar III. (V $\cup$$\Sigma$)* $\rightarrow$ (V $\cup$$\Sigma$)* D. Type 0 Grammar IV. V $\rightarrow$ V$\Sigma$|$\Sigma$
Choose the correct answer from the options given below: Given the recursively enumerable language (\(L_{RE}\)), the context sensitive language (\(L_{CS}\)), the recursive language (\(L_{REC}\)), the context free language (\(L_{CF}\)) and deterministic context free language (\(L_{DCF}\)). The relationship between these families is given by
The family of context sensitive languages is __________ under union and __________ under reversal.
Match the LIST-I with LIST-II
LIST-I LIST-II A. Type - 0 grammar I. Linear Grammar B. Type - 1 grammar II. GNF C. Type - 2 grammar III. x→y, |x|<|y|; x, y ∈ {V ∪ T}* D. Type - 3 grammar IV. Recursively Enumerable Choose the correct answer from the options given below:
