Absolutely!
Here are the questions extracted from the provided text:
Regular Grammar to Regular Expression Conversion
1. Which of the following regular grammars generates the regular expression
a*?
o A) S -> aS | ε
o B) S -> aA, A -> ε
o C) S -> aaS | ε
o D) S -> aS | bA, A -> ε
2. Which of the following is the first step in converting a regular grammar into a
regular expression?
o A) Convert the grammar into an equivalent finite automaton.
o B) Convert the grammar into a context-free grammar.
o C) Eliminate unit productions from the grammar.
o D) Construct regular expression directly from the production rules.
3. The regular grammar S -> aS | bA, A -> b corresponds to which regular
expression?
o A) ab*
o B) a+b
o C) a*b
o D) a*bb
4. Which of the following is the regular expression for the grammar S -> aA ,
A->bS | ε?
o A) ab*
o B) (ab)*
o C) (a|b)*
o D) a*b*
5. What is the equivalent regular expression for the regular grammar S -> aS |
bA, A -> a | b?
o A) (a|b)*
o B) a*b
o C) ab*
o D) (a|b)(a|b)
6. The regular expression corresponding to the grammar S -> aS | bA, A->bA | ε
is:
o A) a*b*
o B) ab*
o C) a+b+
o D) (ab)*
7. To convert the regular expression a*b into a regular grammar, which of the
following production rules is correct?
o A) S -> aS | b
o B) S -> b | aA, A -> aA
o C) S -> aA, A -> aA | b
o D) S -> aS, A -> bS
8. Which regular expression corresponds to the following grammar: S -> aS | b?
o A) a*b
o B) b*a
o C) ab*
o D) b*a
9. Given the regular expression (a|b)*, which set of production rules best
describes the equivalent regular grammar?
o A) S -> aS | bS | ε
o B) S -> aS | bA, A -> a | b
o C) S -> abS | aS
o D) S -> aS | Bs
10. Which of the following is the correct grammar for the regular expression
(ab)*?
o A) S -> aA, A -> bS | ε
o B) S -> aS | b
o C) S -> abS | ε
o D) S -> ab | ba
11. How does the concept of nullable symbols a ect the conversion of a regular
expression into a regular grammar?
o A) Nullable symbols lead to the inclusion of ε-productions in the
grammar.
o B) Nullable symbols must always be eliminated before converting.
o C) Nullable symbols lead to context-sensitive gaps in the grammar.
o D) Nullable symbols prevent the regular grammar from being finite.
12. Which regular expression corresponds to the following grammar: S -> aA, A -
> bS | ε?
o A) ab*
o B) (ab)*
o C) (a|b)*
o D) a*b
13. Converting the regular expression (a|b)b into a regular grammar would result
in which of the following?
o A) S -> aA | bA, A -> b
o B) S -> aS | bS
o C) S -> aA | bB, A -> b, B -> ε
o D) S -> b | aS
14. For the regular expression a+, what is the correct regular grammar?
o A) S -> aS | a
o B) S -> aS | ε
o C) S -> aS | b
o D) S -> a | ε
15. For the grammar S -> aA |b , A -> aS, which regular expression is correct?
o A) (a^n)b
o B) (aa)*
o C) (ab)*
o D) (a|b)*
16. According to the Chomsky hierarchy, which type of language corresponds to
regular grammars?
o A) Type 3
o B) Type 2
o C) Type 1
o D) Type 0
Q17-21. Consider the Grammer G:S -> 0A | 1B | C A -> 01
Identify unit symbols & remove them
17. Which of the following is a unit production in the original grammar?
o A) S -> 1B
o B) A -> 000
o C) S -> C
o D) B -> 11
18. After removing the unit production S -> C, what new production is added to
S?
o A) S -> 0A
o B) S -> 01
o C) S -> 1B
o D) S -> 000
19. What happens to the production B -> A when unit productions are removed?
o A) B -> A remains unchanged.
o B) B -> 11|A.
o C) B -> 11 | 0S | 000.
o D) B -> 000.
20. Which of the following is the correct form of the grammar after eliminating
unit productions?
o A) S -> 0A | 1B | 01, A -> 0S | 000, B -> 11 | 0S | 000, C -> 01
o B) S -> 0A | 1B | C, A -> 0S | 000, B -> 11 | 0S, C -> 01
o C) S -> 0A | 1B | 01, A -> 0S | 11, B -> 11, C -> 01
o D) S -> 0A | 1B , A -> 0S | 000, B -> 11, C -> 01
21. What does the final grammar without unit productions ensure?
A) There are no null productions left.
B) Each production only involves terminals.
C) All unit productions have been removed, and the grammar
generates the same language.
D) The grammar is converted to Chomsky Normal Form.
22. Rightmost derivations are important for:
A) Generating ambiguous grammars.
B) Ensuring deterministic parsers.
C) Implementing LR parsers
D) Reducing the length of derivations.
Q23. The language of a CFG consists of:
A) Strings derivable using leftmost derivations only.
B) Strings derivable from any combination of derivations.
C) Strings derivable from rightmost derivations only.
D) Sentences that can be generated using recursive rules.
Q24. The Pumping Lemma for CFGs is used to:
A) Prove that certain languages are not regular.
B) Prove that certain languages are not context-free.
C) Construct finite automata for regular languages.
D) Simplify the derivation of strings in CFGs.
Q25. Which of the following must hold for a language to be context-free?
A) It must be recognizable by a pushdown automaton.
B) It must be deterministic.
C) It must not contain null productions.
D) It must be described by a right-linear grammar.
Q26. A context-sensitive language is defined by:
A) A linear bounded automaton.
B) A nondeterministic pushdown automaton.
C) A Turing machine with no space restriction.
D) A Turing machine with a finite tape.
Q27. The relation between recursively enumerable sets and recursive sets is such that:
A) Every recursive set is recursively enumerable, but not all recursively
enumerable sets are recursive.
B) Every recursively enumerable set is recursive.
C) Recursive sets cannot be generated by context-sensitive grammars.
D) Recursive sets and recursively enumerable sets are disjoint.
Q28. Chomsky Hierarchy, Type 3 languages are also known as:
A) Regular languages.
B) Context-free languages.
C) Context-sensitive languages.
D) Recursively enumerable languages.
Q29. A language is accepted by a non-deterministic Turing machine, it must be:
A) Recursive.
B) Recursively enumerable.
C) Context-free.
D) Regular.
Q 30. The concept of “closure” in formal languages refers to:
A) The set of all strings over an alphabet.
B) The closure properties of operations like union, intersection, and
complement for a language class.
C) The derivation of strings from the start symbol.
D) The ability of an automation to recognize multiple languages.
_________________________________________________________________________________
_________________________________________________________________________________
Questions:
1. The language generated by a grammar can be described as:
o A) The set of derivations obtained from terminals.
o B) The set of strings derivable from the start symbol using production
rules.
o C) The recursive closure of terminal strings.
o D) The set of all possible words over a given alphabet.
2. Which of the following is the most general class in the Chomsky hierarchy?
o A) Regular languages
o B) Context-free languages
o C) Context-sensitive languages
o D) Recursively enumerable languages
3. A left-linear grammar is one where:
o A) All production rules have terminals on the right.
o B) All production rules have non-terminals on the leftmost position of the
right-hand side of a rule.
o C) Non-terminals appear on the left-hand side of every rule.
o D) Non-terminals always appear at the right.
4. Right-linear grammars are used to describe:
o A) Context-sensitive languages
o B) Context-free languages
o C) Regular languages
o D) Recursive languages
5. The conversion of a regular grammar to a regular expression involves:
o A) Minimization of finite automata.
o B) Eliminating all non-determinism.
o C) Applying Kleene star to all productions.
o D) Rewriting the production rules as algebraic expressions.
6. Regular sets are closed under which of the following operations?
o A) Union, intersection, and complement
o B) Intersection, complement, and di erence
o C) Union, concatenation, and Kleene star
o D) Concatenation, intersection, and di erence
7. Which property di erentiates regular grammars from context-free grammars?
o A) The ability to generate infinite languages.
o B) The limitation of non-terminal symbols to specific positions in rules.
o C) The use of terminal symbols in productions.
o D) The capacity to generate ambiguous languages.
8. A leftmost derivation in a context-free grammar implies:
o A) Non-terminals are replaced from left to right.
o B) Non-terminals are replaced from right to left.
o C) Non-terminals are replaced arbitrarily.
o D) Non-terminals cannot be replaced if they occur on the left.
9. Rightmost derivations are important for:
o A) Generating ambiguous grammars.
o B) Ensuring determinism in derivations.
o C) Implementing LR parsers.
o D) Reducing the length of derivations.
10. The language of CFG consists of:
o A) Strings derivable using leftmost derivations only.
o B) Strings derivable from any combination of derivations.
o C) Strings derivable from rightmost derivations only.
o D) Sentences that can be generated using recursive rules.
11. The Pumping Lemma for CFGs is used to:
o A) Prove that certain languages are not regular.
o B) Prove that certain languages are not context-free.
o C) Construct finite automata for regular languages.
o D) Simplify the derivation of strings in CFGs.
12. Which of the following must hold for a language to be context-free?
o A) It must be recognizable by a pushdown automaton.
o B) It must be deterministic.
o C) It must not contain null productions.
o D) It must be described by a right-linear grammar.
13. The relation between recursively enumerable sets and recursive sets is such
that:
o A) Every recursive set is recursively enumerable, but not all recursively
enumerable sets are recursive.
o B) Every recursively enumerable set is recursive.
o C) Recursive sets cannot be generated by context-sensitive grammars.
o D) Recursive sets and recursively enumerable sets are disjoint.
14. If a language is accepted by a non-deterministic Turing machine, it must be:
o A) Recursive
o B) Recursively enumerable
o C) Context-free
o D) Regular
15. Which of the following operations is not closed for context-free languages?
o A) Union
o B) Intersection
o C) Concatenation
o D) Kleene star
16. The intersection of two context-free languages is:
o A) Always context-free
o B) Sometimes context-free, but not always
o C) Never context-free
o D) Context-sensitive
17. Which of the following statements is true for languages in the Chomsky
hierarchy?
o A) All regular languages are context-free, but not all context-free
languages are regular.
o B) All context-free languages are regular.
o C) All context-sensitive languages are recursively enumerable.
o D) Recursive languages are not closed under union.
18. Which of the following can NOT be recognized by a finite automation?
o A) A string with an equal number of 'a's and 'b's.
o B) A string starting with 'a' and ending with 'b'.
o C) A string with an even number of 'a's.
o D) A string containing no more than three 'a's.
19. A CFG can have all except:
o A) Ambiguity
o B) Leftmost and rightmost derivations
o C) Context-sensitive rules
o D) Production rules with both terminals and non-terminals
20. Which of the following is a necessary condition for a grammar to be context-free?
o A) The right-hand side of any production can have at most two non-
terminals.
o B) Every production must involve only a single non-terminal on the left-
hand side.
o C) The grammar must contain no unit productions.
o D) Every production must have at least one terminal.
21-25. Consider the Grammar G: S -> ABCd, A -> bC, B -> bb | ε, C -> c | ε. Find all of
the nullable variables & remove null productions.
21. After that what are productions associated with B?
o A) B -> bb
o B) B -> ε
o C) B -> bb | ε
o D) B -> b
22. After that what are productions associated with C?
o A) C -> c
o B) C -> ε
o C) C -> c | ε
o D) C -> c | b
23. After that what are productions associated with S?
o A) S -> ABCd
o B) S -> ABCd | ABd | ACd | BCd | Ad | Bd | Cd
o C) S -> ABCd | Ad | Bd
o D) None of these
24. After that what are productions associated with A?
o A) A -> bC
o B) A -> bC | b
o C) A -> bC | B | C
o D) A -> bC | ε
25. Which of the following variables are nullable in the given grammar?
o A) Only B
o B) Only C
o C) Both B and C
o D) A, B, and C
26. Which of the following regular grammars generates the regular expression a*?
o A) S -> aS | ε
o B) S -> aA, A -> ε
o C) S -> aA, A -> aS | ε
o D) S -> aS | b, A -> aAε
27. Which of the following is the first step in converting a regular grammar into a
regular expression?
o A) Convert the grammar into an equivalent finite automaton.
o B) Convert the grammar into a context-free grammar.
o C) Eliminate unit productions from the grammar.
o D) Construct a regular expression directly from the production rules.
28. The regular grammar S -> aS | bA, A -> b corresponds to which regular
expression?
o A) ab*
o B) a*b
o C) a*b
o D) a*bb
29. Which of the following is the regular expression for the grammar S -> aA, A -> b |
ε?
o A) ab*
o B) (ab)*
o C) (a|b)*
o D) a*b*
30) What is the equivalent regular expression for the regular grammar S -> aS |
bA, A -> a | b?
A) (a|b)*
B) a*b
C) ab*
D) a|b)(a|b)
