1What is the primary focus of formal language theory in discrete mathematics?
introduction
Easy
A.The study of continuous physical systems
B.The study of the syntactic structure of strings formed from alphabets
C.The study of human brain activity during speech
D.The study of natural human spoken languages
Correct Answer: The study of the syntactic structure of strings formed from alphabets
Explanation:
Formal language theory in computer science and discrete mathematics focuses on defining languages as sets of strings of symbols based on strict syntactical rules.
Incorrect! Try again.
2In the context of formal languages and automata, what does a computational model represent?
introduction
Easy
A.An abstract mathematical machine that computes or recognizes languages
B.A physical computer processor
C.A programming language like Python
D.A database management system
Correct Answer: An abstract mathematical machine that computes or recognizes languages
Explanation:
A computational model (like an automaton) is an abstract mathematical machine used to study logic, compute functions, and recognize formal languages.
Incorrect! Try again.
3Which mathematical symbol is standardly used to denote an alphabet in formal language theory?
alphabet
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The uppercase Greek letter Sigma () is conventionally used to represent an alphabet, which is a finite set of symbols.
Incorrect! Try again.
4Which of the following best defines an 'alphabet' in the context of discrete mathematics?
alphabet
Easy
A.An infinite sequence of characters
B.A collection of words with specific meanings
C.A finite, non-empty set of symbols
D.A set of grammar rules
Correct Answer: A finite, non-empty set of symbols
Explanation:
An alphabet is formally defined as any finite and non-empty set of basic symbols or characters.
Incorrect! Try again.
5If , what is this specific alphabet commonly called?
alphabet
Easy
A.The decimal alphabet
B.The binary alphabet
C.The empty alphabet
D.The unary alphabet
Correct Answer: The binary alphabet
Explanation:
An alphabet consisting of exactly two symbols, typically 0 and 1, is called the binary alphabet.
Incorrect! Try again.
6What is a 'word' or 'string' over an alphabet ?
words
Easy
A.An infinite loop of characters from
B.A mathematical function mapping to real numbers
C.A finite sequence of symbols chosen from
D.A subset of
Correct Answer: A finite sequence of symbols chosen from
Explanation:
A word (or string) is simply a finite sequence of zero or more symbols drawn from the given alphabet .
Incorrect! Try again.
7What is the length of the empty string (often denoted by or )?
words
Easy
A.Infinite
B.0
C.Undefined
D.1
Correct Answer: 0
Explanation:
The empty string contains no symbols at all, so its length is defined as 0.
Incorrect! Try again.
8If a word is , what is its length, denoted as ?
words
Easy
A.3
B.1
C.4
D.0
Correct Answer: 3
Explanation:
The length of a word is the number of symbols it contains. The word 'abc' contains three symbols, so its length is 3.
Incorrect! Try again.
9What binary operation is used to combine two strings in a free semigroup?
free semigroup
Easy
A.Intersection
B.Cartesian product
C.Addition
D.Concatenation
Correct Answer: Concatenation
Explanation:
In a free semigroup of words over an alphabet, the primary operation is concatenation, which joins two strings end-to-end.
Incorrect! Try again.
10What does the notation represent in formal languages?
free semigroup
Easy
A.The union of two alphabets
B.The empty set
C.The set of all strings over , including the empty string
D.The set of all non-empty strings over
Correct Answer: The set of all non-empty strings over
Explanation:
(the free semigroup) represents the set of all strings of length 1 or more over . It excludes the empty string, unlike .
Incorrect! Try again.
11How is a 'language' formally defined over an alphabet ?
languages and regular languages
Easy
A.Any infinite set of symbols
B.Any element of
C.The power set of
D.Any subset of
Correct Answer: Any subset of
Explanation:
A formal language over an alphabet is defined as a subset of , meaning it is a specific collection of words formed from the alphabet.
Incorrect! Try again.
12Which of the following operations is a standard regular operation used to build regular languages?
languages and regular languages
Easy
A.Factorial
B.Division
C.Kleene star
D.Differentiation
Correct Answer: Kleene star
Explanation:
Regular languages are built using three main regular operations: union, concatenation, and the Kleene star.
Incorrect! Try again.
13What does the regular expression denote?
regular expressions
Easy
A.Zero or more occurrences of 'a'
B.One or more occurrences of 'a'
C.Exactly one occurrence of 'a'
D.No occurrences of 'a'
Correct Answer: Zero or more occurrences of 'a'
Explanation:
The Kleene star () applied to a symbol indicates that the symbol can occur zero or more times in succession.
Incorrect! Try again.
14In regular expressions, what does the symbol or typically represent?
regular expressions
Easy
A.Concatenation
B.Intersection
C.Kleene star
D.Union (or logical OR)
Correct Answer: Union (or logical OR)
Explanation:
In standard regular expression notation, the or symbol is used to represent the union of two expressions, offering a choice between them.
Incorrect! Try again.
15Which regular expression represents the set of binary strings consisting of a single '0' or a single '1'?
regular expressions
Easy
A.
B.
C.
D.$01$
Correct Answer:
Explanation:
The expression (or ) matches either the exact string '0' or the exact string '1'.
Incorrect! Try again.
16What does the acronym DFA stand for in automata theory?
finite state automata
Easy
A.Deterministic Finite Automaton
B.Digital Finite Architecture
C.Discrete Function Algorithm
D.Deterministic Formula Application
Correct Answer: Deterministic Finite Automaton
Explanation:
DFA stands for Deterministic Finite Automaton, a finite state machine that accepts or rejects strings of symbols and produces a unique computation for each input string.
Incorrect! Try again.
17In a finite state automaton, what is the purpose of an 'accepting' or 'final' state?
finite state automata
Easy
A.To halt the machine permanently regardless of input
B.To reset the machine to its start state
C.To indicate that the input string is valid and belongs to the language
D.To output an error message
Correct Answer: To indicate that the input string is valid and belongs to the language
Explanation:
If an automaton finishes reading an input string and lands in an accepting (or final) state, it means the string is accepted as part of the language.
Incorrect! Try again.
18A Deterministic Finite Automaton (DFA) is formally defined mathematically as a tuple with how many elements?
finite state automata
Easy
A.4-tuple
B.7-tuple
C.3-tuple
D.5-tuple
Correct Answer: 5-tuple
Explanation:
A DFA is formally defined as a 5-tuple: , representing states, alphabet, transition function, start state, and accept states.
Incorrect! Try again.
19According to the Chomsky hierarchy, which type of grammar generates regular languages?
grammars and types of grammars
Easy
A.Type 2 (Context-free grammars)
B.Type 3 (Regular grammars)
C.Type 0 (Unrestricted grammars)
D.Type 1 (Context-sensitive grammars)
Correct Answer: Type 3 (Regular grammars)
Explanation:
In the Chomsky hierarchy, Type 3 grammars are regular grammars, and they exactly generate the class of regular languages.
Incorrect! Try again.
20A formal grammar consists of variables (non-terminals), terminals, production rules, and what other essential component?
grammars and types of grammars
Easy
A.A blank character
B.An accept state
C.A regular expression
D.A start symbol
Correct Answer: A start symbol
Explanation:
A formal grammar is defined as a 4-tuple , where is the start symbol (or start variable) from which all derivations begin.
Incorrect! Try again.
21If an alphabet is defined as , how many words of length 3 can be formed without repeating any symbols?
alphabet
Medium
A.6
B.9
C.27
D.3
Correct Answer: 6
Explanation:
Since repetitions are not allowed, the first position can be chosen in 3 ways, the second in 2 ways, and the third in 1 way. Total words = .
Incorrect! Try again.
22Let . Which of the following expressions represents the total number of words of length that can be formed over ?
words
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
For an alphabet of size , the number of words of length is . Here, (since ), so there are possible words.
Incorrect! Try again.
23The free semigroup over an alphabet , denoted as , differs from the free monoid because it strictly excludes which of the following?
free semigroup
Medium
A.The set of all single-character words
B.Infinite strings
C.The empty string
D.The universal set
Correct Answer: The empty string
Explanation:
The free monoid includes all possible strings over , including the empty string . The free semigroup excludes , containing only strings of length 1 or greater.
Incorrect! Try again.
24If and are elements of a free semigroup over , what is the length of the concatenated word ?
free semigroup
Medium
A.4
B.8
C.6
D.10
Correct Answer: 6
Explanation:
The word is the concatenation of with itself, resulting in (length 4). Concatenating (length 2) with gives , which has a total length of .
Incorrect! Try again.
25Let and . What is the resulting language of the concatenation ?
languages and regular languages
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The concatenation is formed by taking every string in and appending every string in . This yields followed by , and followed by , resulting in .
Incorrect! Try again.
26Which of the following operations is NOT closed under the class of regular languages?
languages and regular languages
Medium
A.Infinite Union
B.Kleene Star
C.Union
D.Intersection
Correct Answer: Infinite Union
Explanation:
Regular languages are closed under finite union, intersection, and the Kleene star operation. However, they are not closed under infinite union, which can generate non-regular languages.
Incorrect! Try again.
27If is a regular language over an alphabet , what can be conclusively said about its complement (where )?
languages and regular languages
Medium
A. is always context-free but not regular.
B. is always empty.
C. is always a regular language.
D. is always finite.
Correct Answer: is always a regular language.
Explanation:
Regular languages are closed under complementation. If a language is regular, an equivalent Deterministic Finite Automaton (DFA) exists; swapping its accepting and non-accepting states creates a DFA for the complement language.
Incorrect! Try again.
28Which of the following strings is NOT in the language generated by the regular expression ?
regular expressions
Medium
A.$010101$
B.$000$
C.$1001$
D.$110011$
Correct Answer: $010101$
Explanation:
The regular expression describes the set of all binary strings that contain the substring '00'. The string $010101$ does not contain two consecutive zeros, so it is not in the language.
Incorrect! Try again.
29What language is represented by the regular expression ?
regular expressions
Medium
A.Strings starting with 'b' and ending with 'a'
B.Strings where 'a' is immediately followed by 'b'
C.Strings containing at least one 'a' and one 'b'
D.Strings of 'a's and 'b's starting with 'a' and ending with 'b'
Correct Answer: Strings of 'a's and 'b's starting with 'a' and ending with 'b'
Explanation:
The regular expression begins with an 'a', followed by any combination of 'a's and 'b's (including the empty string), and strictly ends with a 'b'.
Incorrect! Try again.
30Which regular expression represents the set of all binary strings with an even number of $0$s (ignoring $1$s)?
regular expressions
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The expression ensures that $0$s come in pairs (hence an even number of $0$s) while allowing any number of $1$s before, between, and after the pairs of $0$s.
Incorrect! Try again.
31If is a regular expression, which of the following is equivalent to the simplified expression ?
regular expressions
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The Kleene star operation already denotes zero or more repetitions of . Applying the star operation again, , does not add any new strings to the language; it is equivalent to .
Incorrect! Try again.
32In a Deterministic Finite Automaton (DFA), what happens if a string finishes processing and the automaton is in a non-accepting state?
finite state automata
Medium
A.The string is rejected.
B.The automaton crashes.
C.The string is reversed and processed again.
D.The string is sent to an error state.
Correct Answer: The string is rejected.
Explanation:
A string is accepted by a DFA if and only if it finishes processing in one of the defined accepting (final) states. Otherwise, the string is rejected.
Incorrect! Try again.
33A DFA is formally defined as a 5-tuple . What does represent in this definition?
finite state automata
Medium
A.The set of accept states
B.The input alphabet
C.The transition function
D.The initial state
Correct Answer: The transition function
Explanation:
In the formal 5-tuple definition of a DFA, represents the transition function, mapping a state and an input symbol to the next state: .
Incorrect! Try again.
34How many states are minimally required for a DFA to accept exactly the set of strings over that end with the substring ?
finite state automata
Medium
A.2
B.5
C.4
D.3
Correct Answer: 3
Explanation:
A minimal DFA for strings ending in requires 3 states: an initial state (nothing matched), a state indicating the previous character was 'a', and an accepting state indicating the previous characters were 'ab'.
Incorrect! Try again.
35Which of the following statements about Nondeterministic Finite Automata (NFAs) and DFAs is mathematically true?
finite state automata
Medium
A.DFAs allow -transitions but NFAs do not.
B.Every NFA can be converted to an equivalent DFA.
C.DFAs typically have fewer states than their equivalent NFAs in the worst case.
D.NFAs can recognize more languages than DFAs.
Correct Answer: Every NFA can be converted to an equivalent DFA.
Explanation:
NFAs and DFAs have the same computational power and recognize exactly the class of regular languages. Using the subset construction algorithm, any NFA can be converted into an equivalent DFA.
Incorrect! Try again.
36An NFA has exactly 4 states. What is the maximum number of states in an equivalent DFA constructed using the subset construction method?
finite state automata
Medium
A.24
B.16
C.4
D.8
Correct Answer: 16
Explanation:
The subset construction method generates a DFA where each state represents a subset of the NFA's states. For an NFA with states, the DFA can have up to states. Here, .
Incorrect! Try again.
37In the Chomsky hierarchy, which type of grammar specifically generates context-free languages?
grammars and types of grammars
Medium
A.Type 3
B.Type 1
C.Type 0
D.Type 2
Correct Answer: Type 2
Explanation:
In the Chomsky hierarchy, Type 0 generates recursively enumerable languages, Type 1 context-sensitive, Type 2 context-free, and Type 3 regular languages.
Incorrect! Try again.
38Consider the grammar with production rules . What language does this grammar generate?
grammars and types of grammars
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Each application of adds exactly one 'a' to the left and one 'b' to the right. The base case terminates it, creating matching counts of 'a' and 'b' ().
Incorrect! Try again.
39Which of the following best characterizes the production rules of a Type 3 (Regular) grammar?
grammars and types of grammars
Medium
A.Productions are of the form where .
B.Productions are strictly of the form or .
C.Productions can have multiple non-terminals on the left-hand side.
D.It can generate the language .
Correct Answer: Productions are strictly of the form or .
Explanation:
Type 3 grammars (regular grammars) are restricted to right-linear (or left-linear) productions, mapping a non-terminal to a single terminal followed by at most one non-terminal () or just a single terminal ().
Incorrect! Try again.
40A grammar is formally defined as a 4-tuple . What does the component represent?
grammars and types of grammars
Medium
A.The set of production rules
B.The set of terminal symbols
C.The set of variables (non-terminals)
D.The start symbol
Correct Answer: The set of terminal symbols
Explanation:
In the 4-tuple definition of a grammar, represents variables (non-terminals), represents terminal symbols (the alphabet of the language), is the productions, and is the start variable.
Incorrect! Try again.
41In the context of formal language theory and theoretical computability, which of the following best describes a fundamental, mathematically proven limitation of formal systems in determining language membership?
introduction
Hard
A.Rice's Theorem dictates that any non-trivial semantic property of the languages recognized by Turing machines is undecidable.
B.The Chomsky-Schützenberger representation theorem states that no algorithmic process can decide whether an arbitrary context-free language is empty.
C.The pumping lemma for unrestricted grammars demonstrates that no formal grammar can recognize non-recursive languages.
D.Myhill's Theorem guarantees that a language is Turing-recognizable if and only if its syntactic monoid is infinite.
Correct Answer: Rice's Theorem dictates that any non-trivial semantic property of the languages recognized by Turing machines is undecidable.
Explanation:
Rice's Theorem proves that all non-trivial properties of the languages computed by Turing machines (recursively enumerable languages) are undecidable, defining a hard mathematical limit on analyzing formal languages algorithmically.
Incorrect! Try again.
42Let be an uncountably infinite alphabet. Which of the following statements rigorously holds true regarding the set of all finite words and the power set of , denoted ?
alphabet
Hard
A. is uncountable, but remains undefined because formal languages strictly require finite alphabets.
B. is countably infinite because words are of finite length, but is uncountably infinite.
C. is uncountably infinite, and has a strictly greater uncountable cardinality than .
D.Both and possess the exact same uncountable cardinality due to the properties of Kleene closure on uncountable sets.
Correct Answer: is uncountably infinite, and has a strictly greater uncountable cardinality than .
Explanation:
If is uncountable, taking finite sequences (words) maintains an uncountable cardinality (specifically, ). By Cantor's theorem, the power set of any set has a strictly greater cardinality than , meaning .
Incorrect! Try again.
43According to the Fine and Wilf theorem (periodicity lemma) in combinatorics on words, if a word has periods and , what is the mathematically necessary and sufficient condition on the length of to guarantee that also has a period of ?
words
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The Fine and Wilf theorem states that if a word has periods and and its length is at least , then it must also have a period of . This bound is tight and optimal.
Incorrect! Try again.
44Let and be non-empty words over an alphabet . If the commutation equation holds true, which of the following is an inevitable structural consequence for and ?
words
Hard
A.The length of must be an exact multiple of the length of , or vice-versa.
B.There exists a primitive word such that and for some positive integers .
C. and must be palindromes of each other.
D.The words and must have the exact same length and be identical ().
Correct Answer: There exists a primitive word such that and for some positive integers .
Explanation:
A fundamental result in combinatorics on words states that two non-empty words commute () if and only if they are powers of the same common root word. Taking the shortest such root gives a primitive word .
Incorrect! Try again.
45Let be an arbitrary semigroup. The free semigroup on a generating set , denoted , is characterized by a specific universal mapping property. Which of the following statements mathematically captures this freeness property?
free semigroup
Hard
A.For any mapping , there exists a unique semigroup homomorphism such that for all .
B.For any mapping , there is an injective homomorphism that preserves the semigroup operation.
C.Every mapping can be bijectively mapped to a unique element in the alphabet .
D.The semigroup is isomorphic to the quotient of by the minimal congruence relation containing .
Correct Answer: For any mapping , there exists a unique semigroup homomorphism such that for all .
Explanation:
The universal property of the free semigroup states that any function from the generators to any semigroup can be uniquely extended to a semigroup homomorphism from to . This mathematically encodes the lack of 'relations' among elements in .
Incorrect! Try again.
46Consider the free semigroup over and a congruence relation defined such that for any , if and only if they have the same length modulo 3. What is the algebraic structure of the quotient semigroup ?
free semigroup
Hard
A.It is an infinite semigroup consisting of three disjoint sub-semigroups.
B.It is a finite semigroup that fails to be a group because it lacks an identity element (the empty word is not in ).
C.It is a free monoid of rank 3.
D.It is a finite semigroup mathematically isomorphic to the cyclic group .
Correct Answer: It is a finite semigroup mathematically isomorphic to the cyclic group .
Explanation:
The quotient elements correspond to words of length $1, 2$, and . Concatenating words adds their lengths modulo $3$. Thus, the operation acts like addition in . Since length acts as an identity element, it forms a group isomorphic to .
Incorrect! Try again.
47Using the Myhill-Nerode theorem, what is the exact number of equivalence classes of the indistinguishability relation for the language ?
languages and regular languages
Hard
A.Exactly where is the length of the longest string evaluated, because subset construction cannot determinize it in finite states.
B.Exactly two, representing whether a string currently has an equal number of 0s and 1s or an unequal number.
C.Countably infinite, because every unique difference between the count of 0s and 1s in a prefix requires a distinct equivalence class.
D.Uncountably infinite, as every real number configuration of ratios between 0s and 1s maps to a unique state.
Correct Answer: Countably infinite, because every unique difference between the count of 0s and 1s in a prefix requires a distinct equivalence class.
Explanation:
Under the Myhill-Nerode theorem, two prefixes and are indistinguishable if and only if they require the exact same suffix to reach an equal count of 0s and 1s. This means they must have the same difference between 0s and 1s. Since this difference can be any integer (e.g., ), there is a countably infinite number of equivalence classes. Consequently, is not regular.
Incorrect! Try again.
48Let be a regular language and be an arbitrary, non-regular language. The right quotient of with respect to is defined as . What can be guaranteed about the language ?
languages and regular languages
Hard
A. is always a non-regular language.
B. is regular if and only if is a context-free language.
C.The regularity of depends entirely on the algebraic structure of and is generally undecidable.
D. is always a regular language.
Correct Answer: is always a regular language.
Explanation:
The right quotient of a regular language by any language (even non-regular or uncomputable ones) is always regular. This is proven by taking the DFA for and simply changing the set of accepting states to those states from which an original accept state can be reached via a string in .
Incorrect! Try again.
49Which of the following is an accurate synthesis of the closure properties of strictly non-regular languages?
languages and regular languages
Hard
A.They are closed under complementation, but not under union or intersection.
B.They are closed under union and intersection, but not under Kleene star.
C.They are not closed under union, intersection, or complementation.
D.They are closed under intersection with regular languages, but not closed under complementation.
Correct Answer: They are not closed under union, intersection, or complementation.
Explanation:
Non-regular languages are not closed under union (e.g., , which is regular), intersection (e.g., disjoint non-regular languages yield the empty set, which is regular), or complementation (the complement of a non-regular language is non-regular, which technically means they are closed under complement. Wait! If is non-regular, must be non-regular because if were regular, would be regular. Therefore, non-regular languages ARE closed under complementation. Wait, let me re-evaluate.) Self-correction: If is non-regular, its complement is also non-regular. Thus, the set of non-regular languages IS closed under complementation. The correct option must be the one asserting they are closed under complementation but not union/intersection.
Incorrect! Try again.
50By applying Arden's Theorem, consider the language equation , where and are regular languages. If the empty string , what is the unique solution for ?
regular expressions
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Arden's Theorem states that an equation of the form has a unique solution provided that the language does not contain the empty string .
Incorrect! Try again.
51The Brzozowski derivative of a regular expression with respect to a symbol , denoted , describes the language . What is the derivative ?
regular expressions
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Using the rules of Brzozowski derivatives, . Here, . Therefore, .
Incorrect! Try again.
52Which of the following algebraic identities involving regular expressions and is mathematically FALSE in general?
regular expressions
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The expression generates strings consisting of any mixture of elements from and . In contrast, only generates strings that are entirely made of elements from , or entirely made of elements from . Therefore, they are not equivalent.
Incorrect! Try again.
53When converting a Non-deterministic Finite Automaton (NFA) with states to a Deterministic Finite Automaton (DFA) using the subset construction, the worst-case number of reachable states in the resulting minimal DFA is . Which canonical language requires exactly states in its minimal DFA while only needing states in an NFA?
finite state automata
Hard
A.The language of strings over where the -th symbol from the right is '1'.
B.The language of strings over containing exactly occurrences of '1'.
C.The language of palindromes of length at most .
D.The language of strings over where the -th symbol from the left is '1'.
Correct Answer: The language of strings over where the -th symbol from the right is '1'.
Explanation:
An NFA can simply guess when it is exactly steps from the end and check if the current symbol is '1' (requiring states). A DFA, however, must explicitly remember the last symbols seen at any given time, requiring states.
Incorrect! Try again.
54Let be a minimal DFA recognizing a language . We construct an NFA for the reverse language by reversing all transition directions, designating as the sole accept state, and creating a new start state with -transitions to all states in . In the worst case, what is the minimum number of states required when this resulting NFA is determinized back into a DFA?
finite state automata
Hard
A.Exactly states, because the structural minimization of regular languages is symmetric under reversal.
B.Up to states, resulting from the cross-product construction of the reversed transitions.
C.Exactly states, to account for the new start state and -transitions.
D.Up to states, as reversing a minimal DFA can produce an NFA whose equivalent minimal DFA is exponentially larger.
Correct Answer: Up to states, as reversing a minimal DFA can produce an NFA whose equivalent minimal DFA is exponentially larger.
Explanation:
The reversal of a regular language recognized by an -state minimal DFA can require up to states for its minimal DFA. The intermediate construction yields an -state NFA (plus a start state), which subset construction can blow up exponentially.
Incorrect! Try again.
55Consider a DFA with states. If the DFA accepts at least one string, what is the strict theoretical upper bound on the length of the shortest accepted string?
finite state automata
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
If a DFA with states accepts any string, the shortest path from the start state to an accepting state cannot contain any cycles. A cycle-free path in a graph with nodes has a maximum length of edges.
Incorrect! Try again.
56Two DFAs, and , have and states respectively. When constructing the minimal DFA for the intersection language , what is the maximum possible state complexity (number of states) of the resulting minimal DFA?
finite state automata
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
By the product automaton construction, tracking the state of and simultaneously yields a state space of , which has a size of . In the worst-case scenario, all these states can be reachable and pairwise distinguishable, making the tight upper bound.
Incorrect! Try again.
57In the Chomsky Hierarchy, Context-Sensitive Grammars (CSGs) are characterized by productions of the form . What is the critical structural restriction that mathematically prevents CSGs from generating all recursively enumerable languages?
grammars and types of grammars
Hard
A.The grammar cannot contain more non-terminal symbols than the length of the longest string it produces.
B.The left side must consist of a single non-terminal symbol surrounded by terminal context strings.
C.Derivations must be strictly applied in a leftmost fashion to prevent infinite recursive looping.
D.The length of the string on the right side of the production must be greater than or equal to the length of the string on the left side ().
Correct Answer: The length of the string on the right side of the production must be greater than or equal to the length of the string on the left side ().
Explanation:
The defining non-contracting property of Context-Sensitive Grammars is that . This prevents the string length from shrinking during derivation (except possibly for producing under special conditions), mapping their power directly to Linear Bounded Automata rather than full Turing Machines.
Incorrect! Try again.
58Let be a Context-Free Grammar strictly in Chomsky Normal Form (CNF). If derives a terminal string of length , exactly how many derivation steps (rule applications) are mathematically required to produce ?
grammars and types of grammars
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
In Chomsky Normal Form, all productions are either or . To produce a string of terminals, exactly binary branching rules () are required to create variables, and exactly terminal rules () are required to convert them. Total steps: .
Incorrect! Try again.
59An inherently ambiguous context-free language is a language for which every possible context-free grammar generating it is ambiguous. Which of the following defines a classic inherently ambiguous language?
grammars and types of grammars
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
This is the canonical example of inherent ambiguity. Any CFG that generates this language must use different parsing strategies for the and constraints. Consequently, strings of the form (where the subsets overlap) will inherently possess at least two distinct parse trees in any such grammar.
Incorrect! Try again.
60Ogden's Lemma is an advanced generalization of the standard Pumping Lemma for Context-Free Languages (CFLs). What specific analytical advantage does Ogden's Lemma provide over the standard CFL Pumping Lemma?
grammars and types of grammars
Hard
A.It allows pumping and in a downward direction only (i.e., ), avoiding the need to test infinite string expansions.
B.It proves that all context-free languages are closed under intersection and complementation by pumping variables independently.
C.It allows the designation of specific positions in a string as 'distinguished,' guaranteeing the pumped substrings contain at least one distinguished position, thereby proving non-context-freeness for edge-case languages.
D.It determines whether an ambiguous context-free grammar can be determinized into an LR(1) grammar by isolating the pumping length.
Correct Answer: It allows the designation of specific positions in a string as 'distinguished,' guaranteeing the pumped substrings contain at least one distinguished position, thereby proving non-context-freeness for edge-case languages.
Explanation:
Ogden's Lemma enhances the Pumping Lemma by allowing the prover to mark certain symbols as 'distinguished'. The lemma guarantees that the pumped parts and will contain at least one distinguished symbol. This allows provers to strategically force the pumping to occur in specific, contradiction-producing segments of a string, working around cases where the standard pumping lemma is too weak.