Question 1

Which of the following denotes Chomskianhiearchy?

Accepted Answer

The Chomsky hierarchy classifies formal grammars according to their generative power. It consists of four levels: Regular (REG), Context-Free (CFL), Context-Sensitive (CSL), and Recursively Enumerable (type 0), in increasing order of generative power.

Question 2

The concept of FSA is much used in this part of the compiler

Accepted Answer

Finite State Automata (FSA) are primarily used in the lexical analysis phase of a compiler to recognize patterns in the source code, such as keywords, operators, and identifiers.

Question 3

The following grammar G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S ? aAB**spaceAB ? CD**spaceCD ? CE**spaceC ? aC**spaceC ? b**spacebE ? bc is

Accepted Answer

C

Question 4

The following CFG is in S ? aBB**spaceB ? bAA**spaceA ? a**spaceB ? b

Accepted Answer

The answer of The following CFG is in S ?...

Question 5

Which of the following statements is wrong?

Accepted Answer

Context Sensitive Grammars (CSGs) generate context-sensitive languages, which are more powerful than the languages recognized by Finite State Machines (FSMs). FSMs can recognize regular languages, which are a subset of context-sensitive languages. Therefore, CSGs cannot be recognized by FSMs due to the limitations in computational power of FSMs.

Question 6

Context free grammar is not closed under

Accepted Answer

Context-free grammars are closed under union, concatenation (product operation), and Kleene star, but they are not closed under complementation. This means that the complement of a language generated by a context-free grammar may not always be generated by any context-free grammar.

Question 7

Let the class of language accepted by finite state machine be L₁ and the class of languages represented by regular expressions be L₂ then

Accepted Answer

The class of languages accepted by finite state machines (FSMs) is exactly the same as the class of languages that can be represented by regular expressions. Both describe regular languages.

Question 8

Which of the following statement is wrong?

Accepted Answer

Not all languages can be generated by context-free grammars. Context-free grammars can generate many types of languages, including all regular languages and some non-regular languages, but there are languages that are not context-free, such as certain types of counting languages that require more complex structures to be generated.

Question 9

Grammar that produce more than one Parse tree for same sentence is:

Accepted Answer

Ambiguous grammars are those that can produce more than one parse tree for the same sentence, leading to multiple interpretations of the sentence structure.

Question 10

The language accepted by a Push down Automata:

Accepted Answer

Pushdown Automata accept Context-Free Languages, which are classified as Type 2 in the Chomsky hierarchy.

Question 11

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

Accepted Answer

In a non-deterministic Pushdown Automaton (PDA), there can be more than one outgoing edge from a state based on the same input symbol and stack symbol, which typically involves READ (reading an input symbol) or POP (popping a symbol from the stack) operations. This allows for multiple possible transitions from a given state, making the PDA non-deterministic.

Question 12

Let L be a language defined over an alphabet ?,then the language of strings , defined over ?, not belonging to L denoted by LC or L. is called :

Accepted Answer

The complement of a language L, denoted by $L^C$ or $\overline{L}$, consists of all strings over the alphabet that are not in L. This definition aligns with choice B, making it the correct answer.

Question 13

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

Accepted Answer

A context-free grammar (CFG) in Chomsky Normal Form (CNF) cannot generate the null string directly because, by definition, each production rule in CNF must either produce two non-terminal symbols or a single terminal symbol. The null string, being the absence of symbols, cannot be produced by such rules unless the grammar explicitly includes a rule for it, which is not allowed in CNF.

Question 14

Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Accepted Answer

Option B correctly represents the set L because it allows for any number of 0s at the beginning, followed by pairs of 1s (each possibly separated by any number of 0s), ensuring an even number of 1s in total.

Question 15

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

Accepted Answer

The automaton accepts strings that start with any number of b's, followed by an a, followed by any number of a's or b's. This is represented by the regular expression b*a(a+b)*.

Question 16

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Accepted Answer

The difference between a recursive language and a recursively enumerable but not recursive language is not guaranteed to be recursively enumerable. This is because while you can enumerate the words in the recursive language, you cannot effectively enumerate the words not in the recursively enumerable language to remove them, making the operation undecidable.

Question 17

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?

Accepted Answer

The answer of Let L denotes the language generated by...

Question 18

Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Accepted Answer

S and T both represent the set of all strings over {a,b}.

Question 19

Which of the following pairs have DIFFERENT expressive power?

Accepted Answer

Deterministic push down automata (DPDA) and Non-deterministic pushdown automata (NPDA) have different expressive powers because there are some context-free languages that can be recognized by an NPDA but not by any DPDA. For example, the language consisting of strings with the form $a^n b^n c^n$ (for $n \geq 0$) can be recognized by an NPDA but not by any DPDA.

Question 20

Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression
1) Syntax analysis**spaceQ. Push down automata
2) Code Generation**spaceR. Dataflow analysis
3) Lexical analysis**spaceS. Register allocation
4) Code optimization

Accepted Answer

Regular Expressions are used in Lexical Analysis (P-3), Push Down Automata are used in Syntax Analysis (Q-1), Dataflow analysis is a technique used in Code Optimization (R-4), and Register Allocation is part of Code Generation (S-2).

Quiz 2: Formal Languages and Automata Theory: Part B

Which of the following denotes Chomskianhiearchy?

The concept of FSA is much used in this part of the compiler

The following grammar G = (N, T, P, S) spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S ? aABspaceAB ? CDspaceCD ? CEspaceC ? aCspaceC ? bspacebE ? bc is

The following CFG is in S ? aBBspaceB ? bAAspaceA ? a**spaceB ? b

Which of the following statements is wrong?

Context free grammar is not closed under

Let the class of language accepted by finite state machine be L₁ and the class of languages represented by regular expressions be L₂ then

Which of the following statement is wrong?

Grammar that produce more than one Parse tree for same sentence is:

The language accepted by a Push down Automata:

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

Let L be a language defined over an alphabet ?,then the language of strings , defined over ?, not belonging to L denoted by LC or L. is called :

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

Let L={w (0 + 1) * w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?

Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b) *, respectively. Which of the following is true?

Which of the following pairs have DIFFERENT expressive power?

Match all items in Group 1 with correct options from those given in Group 2. List I List IIspaceP. Regular Expression 1) Syntax analysisspaceQ. Push down automata 2) Code GenerationspaceR. Dataflow analysis 3) Lexical analysisspaceS. Register allocation 4) Code optimization

Quiz 2: Formal Languages and Automata Theory: Part B

Which of the following denotes Chomskianhiearchy?

The concept of FSA is much used in this part of the compiler

The following grammar G = (N, T, P, S) **spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S ? aAB**spaceAB ? CD**spaceCD ? CE**spaceC ? aC**spaceC ? b**spacebE ? bc is

The following CFG is in S ? aBB**spaceB ? bAA**spaceA ? a**spaceB ? b

Which of the following statements is wrong?

Context free grammar is not closed under

Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then

Which of the following statement is wrong?

Grammar that produce more than one Parse tree for same sentence is:

The language accepted by a Push down Automata:

The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:

Let L be a language defined over an alphabet ?,then the language of strings , defined over ?, not belonging to L denoted by LC or L. is called :

All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:

Let L={w (0 + 1) * w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Let L denotes the language generated by the grammar S - OSO/00. Which of the following is true?

Let S and T be language over ={a,b} represented by the regular expressions (a+b*) * and (a+b) *, respectively. Which of the following is true?

Which of the following pairs have DIFFERENT expressive power?

Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1) Syntax analysis**spaceQ. Push down automata 2) Code Generation**spaceR. Dataflow analysis 3) Lexical analysis**spaceS. Register allocation 4) Code optimization

The following grammar G = (N, T, P, S) spaceN = {S, A, B, C, D, E}spaceT = {a, b, c}spaceP : S ? aABspaceAB ? CDspaceCD ? CEspaceC ? aCspaceC ? bspacebE ? bc is

The following CFG is in S ? aBBspaceB ? bAAspaceA ? a**spaceB ? b

Let the class of language accepted by finite state machine be L₁ and the class of languages represented by regular expressions be L₂ then

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Let S and T be language over ={a,b} represented by the regular expressions (a+b) and (a+b) *, respectively. Which of the following is true?

Match all items in Group 1 with correct options from those given in Group 2. List I List IIspaceP. Regular Expression 1) Syntax analysisspaceQ. Push down automata 2) Code GenerationspaceR. Dataflow analysis 3) Lexical analysisspaceS. Register allocation 4) Code optimization