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.An empty set ()
B.The set of all production rules
C.The universal language
D.The start symbol
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.The process of converting an NFA to a DFA
B.A graph showing the states of an automaton
C.The complement of a regular language
D.A sequence of production rule applications replacing non-terminals to generate a string
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 leftmost non-terminal in the current sentential form
B.The rightmost non-terminal in the current sentential form
C.Any randomly chosen non-terminal
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.A production rule of the form
B.A string containing strictly terminal symbols
C.The final state of an accepting automaton
D.Any string in that can be derived from the start symbol
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.Context-Free Languages
B.Regular Languages
C.Recursively Enumerable Languages
D.Context-Sensitive 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 2
B.Type 1
C.Type 0
D.Type 3
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.
B.
C. must be strictly empty
D. must be a single non-terminal
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 if is the last symbol of the string
B.Any non-terminal can derive once
C. is allowed provided does not appear on the right side of any production
D.There are absolutely no exceptions
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 right-hand side must consist of exactly one terminal and one non-terminal
B.The left-hand side must consist of exactly one non-terminal
C.The left-hand side must contain at least one terminal
D.The length of the left side must be less than the right side
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 can freely mix left-linear and right-linear forms in the same grammar
B.Rules must be strictly either right-linear or strictly left-linear
C.Rules must be of the form where
D.Rules must have exactly one non-terminal on the left and any string on the right
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. cannot be empty
C. must strictly contain only terminals
D.There are absolutely no restrictions on either or
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.Linear Bounded Automaton
B.Finite Automaton
C.Turing Machine
D.Pushdown 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.Pushdown Automaton
B.Finite Automaton
C.Turing Machine
D.Linear Bounded 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.Finite Automaton
C.Turing Machine
D.Linear Bounded Automaton
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.Turing Machine
B.Linear Bounded Automaton
C.Pushdown Automaton
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.There exists a Turing Machine that accepts strings in but may loop forever on strings not in .
B.It requires infinite time to compute.
C.There exists a Turing Machine that halts on every input string, accepting if it is in and rejecting if it is not.
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.There exists a Turing Machine that always halts on all inputs.
B.It has a finite number of strings.
C.There exists a Turing Machine that halts and accepts if a string is in , but may loop indefinitely if the string is not in .
D.It can be parsed using a regular expression.
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 a Context-Free Language.
D.It is always Recursive.
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 Regular.
C.It is strictly Context-Free.
D.It is not Recursively Enumerable.
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.If a language and its complement are both Recursively Enumerable, then is Recursive.
C.Every Regular language is Context-Free.
D.If a language is Context-Free, it must be 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 not even Recursively Enumerable.
B.It is a Regular Language.
C.It is Recursively Enumerable but not Recursive.
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.Recursively Enumerable only
C.Context-Free
D.Context-Sensitive but not Context-Free
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, but only if they are ambiguous.
C.Yes, the intersection of two CFLs is always a CFL.
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. or (where is a terminal string)
B. or (where is a terminal string)
C.
D. only
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. only
B. or (where is a terminal string)
C. or (where is a terminal string)
D.
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.Regular Grammar
B.Unrestricted Grammar strictly
C.Linear Grammar
D.Context-Sensitive Grammar strictly
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.
B.A Context-Sensitive Language that is not Regular
C.A Regular Set (Regular Language)
D.A strictly Finite Set
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.Complement
B.Intersection
C.Infinite Union
D.Finite Union
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.Converting a Context-Free Grammar to Chomsky Normal Form
B.Minimizing the number of states in a DFA
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. and are disjoint sets
B. does not contain the empty string
C. does not contain the empty string
D. is a finite language
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.Yes, every Context-Free Language is Regular.
B.No, Context-Free Languages are a strict subset of Regular Languages.
C.No, Regular Languages are a strict subset of Context-Free Languages.
D.Yes, but only if it contains the empty string.
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.Linear Language
B.Regular Language
C.Finite Language
D.Context-Sensitive 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 two Recursive languages is always Recursive.
B.The union of two RE languages is never RE.
C.The union of a Recursive language and a Regular language is Context-Free.
D.The union of two Recursive languages is Recursively Enumerable but not Recursive.
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 2 (Context-Free Grammar)
B.Type 1 (Context-Sensitive Grammar)
C.Type 3 (Regular Grammar)
D.Type 0 (Unrestricted 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).
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →