Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Tests > Test: Context-Free Grammars & Push-Down Automata - Computer Science Engineering (CSE) MCQ

Test Description

Test: Context-Free Grammars & Push-Down Automata for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Context-Free Grammars & Push-Down Automata questions and answers have been prepared
according to the Computer Science Engineering (CSE) exam syllabus.The Test: Context-Free Grammars & Push-Down Automata MCQs are made for Computer Science Engineering (CSE) 2024 Exam.
Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Context-Free Grammars & Push-Down Automata below.

Solutions of Test: Context-Free Grammars & Push-Down Automata questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Context-Free Grammars & Push-Down Automata solutions in
Hindi for Computer Science Engineering (CSE) course.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Context-Free Grammars & Push-Down Automata | 30 questions in 90 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions

Test: Context-Free Grammars & Push-Down Automata - Question 1

Consider the following languages.

**Q. Which one of the following statements is FALSE?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 1

Test: Context-Free Grammars & Push-Down Automata - Question 2

Which of the following pairs have DIFFERENT expressive power?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 2

1 Crore+ students have signed up on EduRev. Have you? Download the App |

Test: Context-Free Grammars & Push-Down Automata - Question 3

Let P be a regular language and Q be context-free language such that (For example, let P be the language represented by the regular expression p*q* and Q be {p^{n}q^{n}|}). Then which of the following is ALWAYS regular?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 3

Test: Context-Free Grammars & Push-Down Automata - Question 4

Consider the language L1,L2,L3 as given below.

Which of the following statements is **NOT TRUE**?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 4

Test: Context-Free Grammars & Push-Down Automata - Question 5

Consider the languages L1 = {0^{i}1^{j} | i != j}. L2 = {0^{i}1^{j} | i = j}. L3 = {0^{i}1^{j} | i = 2j+1}. L4 = {0^{i}1^{j} | i != 2j}.

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 5

Test: Context-Free Grammars & Push-Down Automata - Question 6

S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 6

Test: Context-Free Grammars & Push-Down Automata - Question 7

Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:

L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0} L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0}

Then L is

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 7

Test: Context-Free Grammars & Push-Down Automata - Question 8

The language L= {0^{i}21^{i} | i≥0 } over the alphabet {0,1, 2} is:

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 8

Test: Context-Free Grammars & Push-Down Automata - Question 9

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

**Q. Which of the following strings is generated by the grammar?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 9

Test: Context-Free Grammars & Push-Down Automata - Question 10

For the correct answer strings to above question, how many derivation trees are there?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 10

Test: Context-Free Grammars & Push-Down Automata - Question 11

Here, w^{r} is the reverse of the string w. Which of these languages are deterministic Context-free languages?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 11

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 12

Test: Context-Free Grammars & Push-Down Automata - Question 13

Consider the following statements about the context free grammar

G = {S → SS, S → ab, S → ba, S → Ε}

I. G is ambiguous

II. G produces all strings with equal number of a’s and b’s

III. G can be accepted by a deterministic PDA.

**Q. Which combination below expresses all the true statements about G?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 13

Test: Context-Free Grammars & Push-Down Automata - Question 14

Which one of the following grammars generates the language L = {a^{i}b^{j} | i ≠ j}

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 14

Test: Context-Free Grammars & Push-Down Automata - Question 15

In the correct grammar of above question, what is the length of the derivation (number of steps starring from S) to generate the string a^{l}b^{m} with l ≠ m?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 15

Test: Context-Free Grammars & Push-Down Automata - Question 16

Consider the languages:

L1 = {a^{n}b^{n}c^{m} | n, m > 0} L2 = {a^{n}b^{m}c^{m} | n, m > 0}

**Q. Which one of the following statements is FALSE?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 16

Test: Context-Free Grammars & Push-Down Automata - Question 17

Consider the languages:

L1 = {ww^{R} |w ∈ {0, 1}*}

L2 = {w#w^{R} | w ∈ {0, 1}*}, where # is a special symbol

L3 = {ww | w ∈ (0, 1}*)

**Q. Which one of the following is TRUE?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 17

Test: Context-Free Grammars & Push-Down Automata - Question 18

The language {a^{m} b^{n} C^{m+n} | m, n ≥ 1} is

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 18

Test: Context-Free Grammars & Push-Down Automata - Question 19

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true ?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 19

Test: Context-Free Grammars & Push-Down Automata - Question 20

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε Which of the following statements is true?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 20

Test: Context-Free Grammars & Push-Down Automata - Question 21

The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 21

Test: Context-Free Grammars & Push-Down Automata - Question 22

Which of the following statements is true?

Test: Context-Free Grammars & Push-Down Automata - Question 23

Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows:

**Q. Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 23

Test: Context-Free Grammars & Push-Down Automata - Question 24

Which of the following languages are context-free?

L1 = {a^{m}b^{n}a^{n}b^{m} ⎪ m, n ≥ 1}

L2 = {a^{m}b^{n}a^{m}b^{n} ⎪ m, n ≥ 1}

L3 = {a^{m}b^{n} ⎪ m = 2n + 1}

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 24

Test: Context-Free Grammars & Push-Down Automata - Question 25

Which one of the following statements is FALSE?

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 25

Test: Context-Free Grammars & Push-Down Automata - Question 26

If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations.

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 26

Test: Context-Free Grammars & Push-Down Automata - Question 27

Consider the following context-free grammars:

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 27

Test: Context-Free Grammars & Push-Down Automata - Question 28

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z_{0}, X} where Z_{0} is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ_{0}) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z_{0} and X (in that order) on the stack.

Test: Context-Free Grammars & Push-Down Automata - Question 29

Consider the following languages.

L_{1} = {a^{i} b^{j} c^{k} | i = j, k ≥ 1}

L_{1} = {a^{i} b^{j} | j = 2i, i ≥ 0}

**Q. Which of the following is true?**

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 29

Test: Context-Free Grammars & Push-Down Automata - Question 30

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is

Detailed Solution for Test: Context-Free Grammars & Push-Down Automata - Question 30

Information about Test: Context-Free Grammars & Push-Down Automata Page

In this test you can find the Exam questions for Test: Context-Free Grammars & Push-Down Automata solved & explained in the simplest way possible.
Besides giving Questions and answers for Test: Context-Free Grammars & Push-Down Automata , EduRev gives you an ample number of Online tests for practice

Download as PDF