1What is the formal definition of a Grammar in Formal Language Theory?
A.
B.
C.
D.
Correct Answer:
Explanation:
A formal grammar is mathematically defined as a 4-tuple , where is a finite set of variables (non-terminals), is a finite set of terminals, is a set of production rules, and is the start symbol.
Incorrect! Try again.
2In the grammar tuple , what does the intersection of and yield?
A.The set of all production rules
B.The start symbol
C.An empty set ()
D.The universal language
Correct Answer: An empty set ()
Explanation:
Variables (non-terminals) and terminals must be strictly disjoint sets. Therefore, their intersection is the empty set.
Incorrect! Try again.
3Which mathematical notation correctly denotes the language generated by a grammar ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The language generated by a grammar consists of all strings of purely terminal symbols () that can be derived from the start symbol in zero or more steps ().
Incorrect! Try again.
4What is a 'derivation' in the context of formal grammars?
A.A sequence of production rule applications replacing non-terminals to generate a string
B.A graph showing the states of an automaton
C.The process of converting an NFA to a DFA
D.The complement of a regular language
Correct Answer: A sequence of production rule applications replacing non-terminals to generate a string
Explanation:
A derivation is a sequence of steps where at each step, a variable (non-terminal) is replaced by the right side of one of its production rules until a string of terminals is formed.
Incorrect! Try again.
5In a leftmost derivation, which non-terminal is replaced at each step?
A.The rightmost non-terminal in the current sentential form
B.Any randomly chosen non-terminal
C.The leftmost non-terminal in the current sentential form
D.The start symbol only
Correct Answer: The leftmost non-terminal in the current sentential form
Explanation:
By definition, a leftmost derivation strictly replaces the leftmost non-terminal present in the sentential form at every step.
Incorrect! Try again.
6What is a sentential form?
A.The final state of an accepting automaton
B.Any string in that can be derived from the start symbol
C.A string containing strictly terminal symbols
D.A production rule of the form
Correct Answer: Any string in that can be derived from the start symbol
Explanation:
If , then is a sentential form. It can contain a mix of both variables and terminals.
Incorrect! Try again.
7According to the Chomsky Hierarchy, Type 0 grammars generate which class of languages?
A.Recursively Enumerable Languages
B.Context-Sensitive Languages
C.Regular Languages
D.Context-Free Languages
Correct Answer: Recursively Enumerable Languages
Explanation:
Type 0 grammars are unrestricted grammars and they generate Recursively Enumerable (RE) languages, recognizable by Turing Machines.
Incorrect! Try again.
8Which type of grammar corresponds to Context-Free Languages in the Chomsky Hierarchy?
A.Type 3
B.Type 2
C.Type 1
D.Type 0
Correct Answer: Type 2
Explanation:
Type 2 grammars are Context-Free Grammars (CFGs) and they generate Context-Free Languages (CFLs).
Incorrect! Try again.
9What is the proper subset relation defining the Chomsky hierarchy, where denotes Type languages?
A.
B.
C.
D.
Correct Answer:
Explanation:
Regular languages () are a subset of Context-Free (), which are a subset of Context-Sensitive (), which are a subset of Recursively Enumerable ().
Incorrect! Try again.
10What is the primary constraint on the production rules for a Type 1 (Context-Sensitive) grammar?
A. must be a single non-terminal
B.
C. must be strictly empty
D.
Correct Answer:
Explanation:
In Type 1 (Context-Sensitive) grammars, the length of the right-hand side string must be greater than or equal to the length of the left-hand side string, making them non-contracting.
Incorrect! Try again.
11What is the only valid exception to the length-increasing rule () in a Context-Sensitive Grammar?
A. is allowed provided does not appear on the right side of any production
B.There are absolutely no exceptions
C. is allowed if is the last symbol of the string
D.Any non-terminal can derive once
Correct Answer: is allowed provided does not appear on the right side of any production
Explanation:
To allow the language to contain the empty string , the start symbol may derive , but cannot appear on the right-hand side of any rule to preserve the non-contracting property for other strings.
Incorrect! Try again.
12What is the defining constraint on the production rules of a Type 2 (Context-Free) grammar?
A.The length of the left side must be less than the right side
B.The right-hand side must consist of exactly one terminal and one non-terminal
C.The left-hand side must consist of exactly one non-terminal
D.The left-hand side must contain at least one terminal
Correct Answer: The left-hand side must consist of exactly one non-terminal
Explanation:
In a Context-Free Grammar (), must be a single non-terminal (). The replacement is independent of the context.
Incorrect! Try again.
13Which of the following describes the production rules for a Type 3 (Regular) grammar?
A.Rules must be of the form where
B.Rules must have exactly one non-terminal on the left and any string on the right
C.Rules can freely mix left-linear and right-linear forms in the same grammar
D.Rules must be strictly either right-linear or strictly left-linear
Correct Answer: Rules must be strictly either right-linear or strictly left-linear
Explanation:
Type 3 grammars (Regular Grammars) must be either purely right-linear (e.g., ) or purely left-linear (e.g., ). Mixing them results in a Linear Grammar, which is Context-Free but not necessarily regular.
Incorrect! Try again.
14What is the only restriction on the production rules for a Type 0 (Unrestricted) grammar?
A. must contain at least one non-terminal
B.There are absolutely no restrictions on either or
C. cannot be empty
D. must strictly contain only terminals
Correct Answer: must contain at least one non-terminal
Explanation:
In an unrestricted grammar, cannot be strictly empty or consist only of terminals; it must have at least one variable (non-terminal) to allow for substitution.
Incorrect! Try again.
15Which computational model strictly corresponds to Recursively Enumerable (Type 0) languages?
A.Turing Machine
B.Finite Automaton
C.Pushdown Automaton
D.Linear Bounded Automaton
Correct Answer: Turing Machine
Explanation:
Turing Machines are capable of recognizing Recursively Enumerable languages, which correspond to Type 0 (Unrestricted) grammars.
Incorrect! Try again.
16Which computational model strictly corresponds to Context-Sensitive (Type 1) languages?
A.Linear Bounded Automaton
B.Pushdown Automaton
C.Turing Machine
D.Finite Automaton
Correct Answer: Linear Bounded Automaton
Explanation:
Linear Bounded Automata (LBAs) are restricted Turing Machines where the tape head cannot move beyond the bounds of the input string. They recognize Context-Sensitive languages.
Incorrect! Try again.
17Which computational model strictly corresponds to Context-Free (Type 2) languages?
A.Pushdown Automaton
B.Linear Bounded Automaton
C.Finite Automaton
D.Turing Machine
Correct Answer: Pushdown Automaton
Explanation:
Pushdown Automata (PDAs) use a stack for memory and are the computational equivalent of Context-Free Grammars.
Incorrect! Try again.
18Which computational model strictly corresponds to Regular (Type 3) languages?
A.Linear Bounded Automaton
B.Pushdown Automaton
C.Turing Machine
D.Finite Automaton
Correct Answer: Finite Automaton
Explanation:
Finite Automata (both Deterministic and Non-Deterministic) recognize Regular Languages.
Incorrect! Try again.
19By definition, a language is called 'Recursive' if:
A.It requires infinite time to compute.
B.There exists a Turing Machine that halts on every input string, accepting if it is in and rejecting if it is not.
C.There exists a Turing Machine that accepts strings in but may loop forever on strings not in .
D.It can be recognized by a Finite Automaton.
Correct Answer: There exists a Turing Machine that halts on every input string, accepting if it is in and rejecting if it is not.
Explanation:
A Recursive language is a decidable language. A Turing Machine will always halt in an accept or reject state for any given input.
Incorrect! Try again.
20By definition, a language is called 'Recursively Enumerable' (RE) if:
A.It can be parsed using a regular expression.
B.There exists a Turing Machine that halts and accepts if a string is in , but may loop indefinitely if the string is not in .
C.There exists a Turing Machine that always halts on all inputs.
D.It has a finite number of strings.
Correct Answer: There exists a Turing Machine that halts and accepts if a string is in , but may loop indefinitely if the string is not in .
Explanation:
For an RE language (semi-decidable), the Turing Machine is only guaranteed to halt and accept valid strings. For invalid strings, it may reject or run forever.
Incorrect! Try again.
21Which of the following is true regarding the complement of a Recursive language?
A.It is Recursively Enumerable but not Recursive.
B.It is never Recursive.
C.It is always Recursive.
D.It is always a Context-Free Language.
Correct Answer: It is always Recursive.
Explanation:
Recursive languages are closed under complementation. If a TM always halts for , we can simply swap the accept and reject states to decide .
Incorrect! Try again.
22What can be said about the complement of a Recursively Enumerable (RE) language that is NOT Recursive?
A.It is always Recursive.
B.It is not Recursively Enumerable.
C.It is Regular.
D.It is strictly Context-Free.
Correct Answer: It is not Recursively Enumerable.
Explanation:
If an RE language is not recursive, its complement cannot be RE. If it were RE, Post's Theorem dictates the language would be Recursive, creating a contradiction.
Incorrect! Try again.
23What does Post's Theorem state regarding formal languages?
A.The intersection of two Context-Free languages is always Context-Free.
B.Every Regular language is Context-Free.
C.If a language is Context-Free, it must be Recursive.
D.If a language and its complement are both Recursively Enumerable, then is Recursive.
Correct Answer: If a language and its complement are both Recursively Enumerable, then is Recursive.
Explanation:
Post's Theorem establishes that a language is decidable (Recursive) if and only if both the language and its complement are semi-decidable (RE).
Incorrect! Try again.
24How is the Halting Problem classified in formal language theory?
A.It is a Regular Language.
B.It is Recursively Enumerable but not Recursive.
C.It is not even Recursively Enumerable.
D.It is Recursive.
Correct Answer: It is Recursively Enumerable but not Recursive.
Explanation:
The Halting Problem is semi-decidable: we can simulate a TM to see if it halts (so it's RE). However, we cannot always determine if it will loop forever, making it undecidable (not Recursive).
Incorrect! Try again.
25The intersection of a Context-Free Language (CFL) and a Regular Language is always:
A.Regular
B.Context-Free
C.Context-Sensitive but not Context-Free
D.Recursively Enumerable only
Correct Answer: Context-Free
Explanation:
Context-Free Languages are closed under intersection with Regular Languages. The cross-product machine of a PDA and a DFA results in a new PDA.
Incorrect! Try again.
26Are Context-Free Languages (CFLs) closed under intersection?
A.No, the intersection is always Regular.
B.Yes, the intersection of two CFLs is always a CFL.
C.Yes, but only if they are ambiguous.
D.No, the intersection of two CFLs is not necessarily a CFL.
Correct Answer: No, the intersection of two CFLs is not necessarily a CFL.
Explanation:
CFLs are not closed under intersection. For example, and are CFLs, but their intersection is Context-Sensitive, not Context-Free.
Incorrect! Try again.
27Which of the following describes the generic form of production rules in a Right-Linear Grammar?
A. only
B. or (where is a terminal string)
C.
D. or (where is a terminal string)
Correct Answer: or (where is a terminal string)
Explanation:
In a right-linear grammar, all non-terminals must appear exclusively at the extreme right end of the right-hand side of a production rule.
Incorrect! Try again.
28Which of the following describes the generic form of production rules in a Left-Linear Grammar?
A. or (where is a terminal string)
B.
C. or (where is a terminal string)
D. only
Correct Answer: or (where is a terminal string)
Explanation:
In a left-linear grammar, all non-terminals must appear exclusively at the extreme left end of the right-hand side of a production rule.
Incorrect! Try again.
29If a grammar freely mixes left-linear rules (e.g., ) and right-linear rules (e.g., ), what type of grammar is it?
A.Unrestricted Grammar strictly
B.Context-Sensitive Grammar strictly
C.Linear Grammar
D.Regular Grammar
Correct Answer: Linear Grammar
Explanation:
A grammar with at most one non-terminal on the right side of any rule is a Linear Grammar. Mixing left and right linearity generates Linear Languages, which are a subset of CFLs but not always Regular.
D.A Context-Sensitive Language that is not Regular
Correct Answer: A Regular Set (Regular Language)
Explanation:
Regular grammars are exactly the syntactic mechanism for generating Regular Sets, equivalent to Regular Expressions and Finite Automata.
Incorrect! Try again.
31Which operation are Regular Languages NOT necessarily closed under?
A.Intersection
B.Infinite Union
C.Finite Union
D.Complement
Correct Answer: Infinite Union
Explanation:
Regular languages are closed under finite union. However, an infinite union of regular languages can yield a non-regular language (e.g., is Context-Free).
Incorrect! Try again.
32Which right-linear regular grammar correctly generates the regular expression ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The regular expression represents a choice between 'a' or 'b'. The grammar directly derives either 'a' or 'b'.
Incorrect! Try again.
33Which right-linear regular grammar correctly generates the regular expression ?
A.
B.
C.
D.
Correct Answer:
Explanation:
The Kleene star operation allows zero or more occurrences of 'a'. generates multiple 'a's, and allows termination, including the empty string.
Incorrect! Try again.
34Which right-linear regular grammar correctly generates the regular expression ?
A.
B.
C.
D.
Correct Answer:
Explanation:
To concatenate 'a' and 'b' sequentially in a right-linear grammar, 'a' transitions to a new non-terminal , which then generates the terminal 'b' and halts.
Incorrect! Try again.
35Arden's Theorem is primarily utilized for which of the following purposes in Formal Language Theory?
A.Minimizing the number of states in a DFA
B.Converting a Context-Free Grammar to Chomsky Normal Form
C.Converting a DFA or Regular Grammar into a Regular Expression
D.Proving that a language is not regular using the Pumping Lemma
Correct Answer: Converting a DFA or Regular Grammar into a Regular Expression
Explanation:
Arden's theorem is used to solve algebraic language equations derived from state transitions or grammar rules to find equivalent Regular Expressions.
Incorrect! Try again.
36Arden's Theorem states that for sets , and , the equation has a unique solution provided what condition is met?
A. does not contain the empty string
B. and are disjoint sets
C. is a finite language
D. does not contain the empty string
Correct Answer: does not contain the empty string
Explanation:
If does not contain , the recursive equation has strictly one unique regular expression solution.
Incorrect! Try again.
37Under Arden's Theorem, if and does not contain , what is the unique solution for ?
A.
B.
C.
D.
Correct Answer:
Explanation:
Substitute into the equation: . Thus, is the correct solution. Note: This solves left-recursive equations.
Incorrect! Try again.
38For the language equation (which arises from right-linear grammars), if does not contain , what is the unique solution for ?
A.
B.
C.
D.
Correct Answer:
Explanation:
Substitute into the equation: . This equation models right-linear rules , giving solution .
Incorrect! Try again.
39Convert the right-linear grammar into an equivalent Regular Expression.
A.
B.
C.
D.
Correct Answer:
Explanation:
This grammar forms the equation (or where ). The derivation yields . The solution is .
Incorrect! Try again.
40Convert the left-linear grammar into an equivalent Regular Expression.
A.
B.
C.
D.
Correct Answer:
Explanation:
This grammar forms the left-recursive equation . Using Arden's Theorem ( with ), the solution is .
Incorrect! Try again.
41Find the regular expression for the right-linear grammar: , .
A.
B.
C.
D.
Correct Answer:
Explanation:
Substitute into . This gives . By solving , the unique solution is $__.
Incorrect! Try again.
42Find the regular expression for the grammar: , .
A.
B.
C.
D.
Correct Answer:
Explanation:
From , we get . Substituting this into , we get (which is equivalent to ).
Incorrect! Try again.
43Is every Context-Free Language also a Regular Language?
A.No, Regular Languages are a strict subset of Context-Free Languages.
B.Yes, but only if it contains the empty string.
C.Yes, every Context-Free Language is Regular.
D.No, Context-Free Languages are a strict subset of Regular Languages.
Correct Answer: No, Regular Languages are a strict subset of Context-Free Languages.
Explanation:
According to the Chomsky hierarchy, Type 3 (Regular) is a proper subset of Type 2 (Context-Free). Thus, not all CFLs are Regular (e.g., is CF but not Regular).
Incorrect! Try again.
44Every Context-Free Language is also a:
A.Context-Sensitive Language
B.Regular Language
C.Finite Language
D.Linear Language
Correct Answer: Context-Sensitive Language
Explanation:
The Chomsky Hierarchy indicates that Type 2 (Context-Free) is a proper subset of Type 1 (Context-Sensitive). Thus, every CFL is inherently Context-Sensitive.
Incorrect! Try again.
45Which of the following languages is strictly Context-Free but NOT Regular?
A.
B.
C.
D.
Correct Answer:
Explanation:
requires matching counts of 'a' and 'b', which requires unbounded memory (a stack), so it cannot be regular, but it can be generated by a CFG.
Incorrect! Try again.
46Which of the following languages is Context-Sensitive but NOT Context-Free?
A.
B.
C.
D.
Correct Answer:
Explanation:
The language requires tracking three dependent counts. A standard PDA (with one stack) cannot match all three, making it non-Context-Free. However, an LBA can track it, making it Context-Sensitive.
Incorrect! Try again.
47Two formal languages and are said to be equivalent if and only if:
A.They share at least one common string
B.They belong to the same Chomsky Hierarchy class
C.They contain exactly the same set of strings ()
D.They are generated by the exact same grammar rules
Correct Answer: They contain exactly the same set of strings ()
Explanation:
By set theory definition, two languages are equivalent if they are identical sets of strings, regardless of the grammar or automaton used to define them.
Incorrect! Try again.
48Which of the following statements about the union of Recursive and Recursively Enumerable languages is TRUE?
A.The union of a Recursive language and a Regular language is Context-Free.
B.The union of two Recursive languages is always Recursive.
C.The union of two Recursive languages is Recursively Enumerable but not Recursive.
D.The union of two RE languages is never RE.
Correct Answer: The union of two Recursive languages is always Recursive.
Explanation:
Recursive languages are closed under union. If TMs and decide and , we can build a TM that simulates both on input and accepts if either accepts; since both halt, the new TM also halts.
Incorrect! Try again.
49What kind of grammar allows rules where the left-hand side can be any string containing at least one non-terminal, and the right-hand side can be shorter than the left-hand side?
A.Type 0 (Unrestricted Grammar)
B.Type 3 (Regular Grammar)
C.Type 2 (Context-Free Grammar)
D.Type 1 (Context-Sensitive Grammar)
Correct Answer: Type 0 (Unrestricted Grammar)
Explanation:
Only Type 0 (Unrestricted) grammars allow contracting rules (where ). Type 1 strictly prohibits this, requiring .
Incorrect! Try again.
50Which automaton corresponds to a language formed by freely mixing left-linear and right-linear grammar rules (A Linear Grammar)?
A Linear Grammar generates a Linear Language, which is a proper subset of Context-Free Languages. Therefore, it is recognized by a Pushdown Automaton, specifically restricted to make at most one turn (transitioning from push to pop).