Theory of Automata MCQs with Answers

Theory of Automata MCQs with Answers by ElecturesAI

Practice 300 Theory of Automata MCQs with answers covering finite automata, DFA, NFA, regular expressions, context-free grammars, pushdown automata, Turing machines, and computational theory.

Theory of Automata MCQs with Answers | ElecturesAI
ElecturesAI

Theory of Automata MCQs with Answers

A complete 300-question practice bank covering formal languages, regular expressions, finite automata, grammars, PDA, Turing machines, decidability and Chomsky Normal Form.

Prepared with dedication by Engnr Dr. Muhammad Tahir Dlbar to help students learn smarter, practice better, and build strong Theory of Automata concepts with confidence.
300MCQs
10Core Areas
FAQSchema Markup

Covered Topics

  • Formal Languages & Stringsalphabets, strings, reverse strings, palindromes, finite and infinite languages42 MCQs
  • Regular Expressionsunion, concatenation, Kleene star, starting/ending patterns and substring expressions24 MCQs
  • Finite AutomataDFA, NFA, transition tables, transition diagrams, complement and Kleene theorem54 MCQs
  • Grammars & DerivationsCFG, regular grammar, terminals, nonterminals, derivations, parse trees and ambiguity60 MCQs
  • Machines with OutputMealy and Moore machines, outputs and conversion methods12 MCQs
  • Non-Regular Languagespumping lemma, Myhill-Nerode theorem and classic nonregular examples18 MCQs
  • Decision Problemsemptiness, equivalence and finiteness checks for automata9 MCQs
  • Pushdown AutomataPDA stack operations, acceptance methods, a^n b^n and palindrome recognition33 MCQs
  • Turing Machines & DecidabilityTuring machine components, configurations, halting and decidable languages30 MCQs
  • Chomsky Normal Formnull productions, unit productions, useless symbols and CNF conversion18 MCQs
300 MCQs showing
Q1 Formal Languages & Strings

What is meant by Formal language in Theory of Automata?

  1. Aan operation that means either expression may be chosen
  2. Ba mathematically defined set of strings over a specified alphabet
  3. Can abstract computational model with a tape, head, states and transition rules
  4. Da finite sequence of symbols chosen from an alphabet
Show Answer
Correct Answer: B. a mathematically defined set of strings over a specified alphabet

Formal language refers to a mathematically defined set of strings over a specified alphabet.

Q2 Formal Languages & Strings

Which option best explains Formal language?

  1. Aa mathematically defined set of strings over a specified alphabet
  2. Ba production that derives the empty string
  3. Ca symbolic notation used to describe regular languages
  4. Dthe expression (0+1)*, which represents every string over {0,1}
Show Answer
Correct Answer: A. a mathematically defined set of strings over a specified alphabet

Formal language refers to a mathematically defined set of strings over a specified alphabet.

Q3 Formal Languages & Strings

A correct statement about Formal language is:

  1. Aa mathematically defined set of strings over a specified alphabet
  2. Ba language containing no strings at all
  3. Cthe string with length zero, usually denoted by ε or lambda
  4. Da finite sequence of symbols chosen from an alphabet
Show Answer
Correct Answer: A. a mathematically defined set of strings over a specified alphabet

Formal language refers to a mathematically defined set of strings over a specified alphabet.

Q4 Formal Languages & Strings

What is meant by Informal language in Theory of Automata?

  1. Athe problem of deciding whether a finite automaton accepts at least one string
  2. Ba state that causes a string to be accepted when input processing ends there
  3. Ca last-in first-out memory structure used by a pushdown automaton
  4. Da natural human language whose meaning may depend on context and everyday usage
Show Answer
Correct Answer: D. a natural human language whose meaning may depend on context and everyday usage

Informal language refers to a natural human language whose meaning may depend on context and everyday usage.

Q5 Formal Languages & Strings

Which option best explains Informal language?

  1. Aa snapshot showing current state, unread input and stack contents
  2. Ba natural human language whose meaning may depend on context and everyday usage
  3. Ca mathematically defined set of strings over a specified alphabet
  4. Dthe method of converting an NFA into an equivalent DFA using sets of NFA states
Show Answer
Correct Answer: B. a natural human language whose meaning may depend on context and everyday usage

Informal language refers to a natural human language whose meaning may depend on context and everyday usage.

Q6 Formal Languages & Strings

A correct statement about Informal language is:

  1. Aan expression such as a(a+b)* over the alphabet {a,b}
  2. Ba rewriting rule that replaces one symbol or pattern with another string
  3. Ca natural human language whose meaning may depend on context and everyday usage
  4. Dthe method of converting an NFA into an equivalent DFA using sets of NFA states
Show Answer
Correct Answer: C. a natural human language whose meaning may depend on context and everyday usage

Informal language refers to a natural human language whose meaning may depend on context and everyday usage.

Q7 Formal Languages & Strings

What is meant by Alphabet in Theory of Automata?

  1. Aa language containing no strings at all
  2. Ba finite non-empty set of symbols used to form strings
  3. Ca tree representation showing how a string is derived from a grammar
  4. Da definition that gives base strings and rules for generating more strings
Show Answer
Correct Answer: B. a finite non-empty set of symbols used to form strings

Alphabet refers to a finite non-empty set of symbols used to form strings.

Q8 Formal Languages & Strings

Which option best explains Alphabet?

  1. Aa method that creates automaton states from grammar variables and transitions from productions
  2. Ba finite non-empty set of symbols used to form strings
  3. Ca CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  4. Dthe number of symbols occurring in a string
Show Answer
Correct Answer: B. a finite non-empty set of symbols used to form strings

Alphabet refers to a finite non-empty set of symbols used to form strings.

Q9 Formal Languages & Strings

A correct statement about Alphabet is:

  1. Athe theorem stating that regular expressions and finite automata define the same class of languages
  2. Ba finite automaton equipped with a stack for recognizing context-free languages
  3. Ca finite non-empty set of symbols used to form strings
  4. Da PDA that guesses the middle of the string and matches the second half using the stack
Show Answer
Correct Answer: C. a finite non-empty set of symbols used to form strings

Alphabet refers to a finite non-empty set of symbols used to form strings.

Q10 Formal Languages & Strings

What is meant by Valid alphabet in Theory of Automata?

  1. Athe number of symbols occurring in a string
  2. Ba language for which some Turing machine halts on every input and decides membership
  3. Can alphabet whose symbols are clearly defined and can be used to build strings
  4. Dany set of strings formed from the symbols of that alphabet
Show Answer
Correct Answer: C. an alphabet whose symbols are clearly defined and can be used to build strings

Valid alphabet refers to an alphabet whose symbols are clearly defined and can be used to build strings.

Q11 Formal Languages & Strings

Which option best explains Valid alphabet?

  1. Aa non-accepting state that the machine cannot escape once entered
  2. Ban alphabet whose symbols are clearly defined and can be used to build strings
  3. Ca definition that gives base strings and rules for generating more strings
  4. Da tree representation showing how a string is derived from a grammar
Show Answer
Correct Answer: B. an alphabet whose symbols are clearly defined and can be used to build strings

Valid alphabet refers to an alphabet whose symbols are clearly defined and can be used to build strings.

Q12 Formal Languages & Strings

A correct statement about Valid alphabet is:

  1. Aan expression such as (a+b)*ab(a+b)* over {a,b}
  2. Ban alphabet whose symbols are clearly defined and can be used to build strings
  3. Cany string of terminals and nonterminals produced during a derivation
  4. Da derivation that always replaces the rightmost nonterminal first
Show Answer
Correct Answer: B. an alphabet whose symbols are clearly defined and can be used to build strings

Valid alphabet refers to an alphabet whose symbols are clearly defined and can be used to build strings.

Q13 Formal Languages & Strings

What is meant by String in Theory of Automata?

  1. Aa Turing machine strategy that repeatedly marks matching a's and b's
  2. Ba finite sequence of symbols chosen from an alphabet
  3. Can unbounded memory divided into cells that can hold symbols
  4. Da problem whose answer is either yes or no
Show Answer
Correct Answer: B. a finite sequence of symbols chosen from an alphabet

String refers to a finite sequence of symbols chosen from an alphabet.

Q14 Formal Languages & Strings

Which option best explains String?

  1. Athe classic nonregular language containing equal numbers of a's followed by b's
  2. Bthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  3. Ca finite sequence of symbols chosen from an alphabet
  4. Da CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
Show Answer
Correct Answer: C. a finite sequence of symbols chosen from an alphabet

String refers to a finite sequence of symbols chosen from an alphabet.

Q15 Formal Languages & Strings

A correct statement about String is:

  1. Aa move that changes state without consuming an input symbol
  2. Ba finite sequence of symbols chosen from an alphabet
  3. Cthe property that a problem has an algorithm that always halts with a yes or no answer
  4. Dan abstract computational model with a tape, head, states and transition rules
Show Answer
Correct Answer: B. a finite sequence of symbols chosen from an alphabet

String refers to a finite sequence of symbols chosen from an alphabet.

Q16 Formal Languages & Strings

What is meant by Empty string in Theory of Automata?

  1. Athe string with length zero, usually denoted by ε or lambda
  2. Ba non-accepting state that the machine cannot escape once entered
  3. Ca string that reads the same from left to right and right to left
  4. Da process that removes null, unit and useless productions and converts long rules into binary form
Show Answer
Correct Answer: A. the string with length zero, usually denoted by ε or lambda

Empty string refers to the string with length zero, usually denoted by ε or lambda.

Q17 Formal Languages & Strings

Which option best explains Empty string?

  1. Athe string with length zero, usually denoted by ε or lambda
  2. Bany set of strings formed from the symbols of that alphabet
  3. Ca move that changes state without consuming an input symbol
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: A. the string with length zero, usually denoted by ε or lambda

Empty string refers to the string with length zero, usually denoted by ε or lambda.

Q18 Formal Languages & Strings

A correct statement about Empty string is:

  1. Aa method that creates automaton states from grammar variables and transitions from productions
  2. Ba grammar in which every generated string has only one parse tree
  3. Cthe string with length zero, usually denoted by ε or lambda
  4. Dan unbounded memory divided into cells that can hold symbols
Show Answer
Correct Answer: C. the string with length zero, usually denoted by ε or lambda

Empty string refers to the string with length zero, usually denoted by ε or lambda.

Q19 Formal Languages & Strings

What is meant by Length of a string in Theory of Automata?

  1. Athe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  2. Ba variable that can derive the empty string
  3. Cthe number of symbols occurring in a string
  4. Da last-in first-out memory structure used by a pushdown automaton
Show Answer
Correct Answer: C. the number of symbols occurring in a string

Length of a string refers to the number of symbols occurring in a string.

Q20 Formal Languages & Strings

Which option best explains Length of a string?

  1. Aa derivation that always replaces the leftmost nonterminal first
  2. Bthe number of symbols occurring in a string
  3. Cthe action of consuming an input symbol while making a transition
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: B. the number of symbols occurring in a string

Length of a string refers to the number of symbols occurring in a string.

Q21 Formal Languages & Strings

A correct statement about Length of a string is:

  1. Aa production of the form A→B where both sides are single variables
  2. Bthe string obtained by writing the original symbols in the opposite order
  3. Cthe number of symbols occurring in a string
  4. Da language containing no strings at all
Show Answer
Correct Answer: C. the number of symbols occurring in a string

Length of a string refers to the number of symbols occurring in a string.

Q22 Formal Languages & Strings

What is meant by Reverse of a string in Theory of Automata?

  1. Athe string obtained by writing the original symbols in the opposite order
  2. BPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  3. Ca grammar with productions restricted to right-linear or left-linear form
  4. Da Turing machine strategy that repeatedly marks matching a's and b's
Show Answer
Correct Answer: A. the string obtained by writing the original symbols in the opposite order

Reverse of a string refers to the string obtained by writing the original symbols in the opposite order.

Q23 Formal Languages & Strings

Which option best explains Reverse of a string?

  1. Aa finite-state machine whose output depends on the current state and input symbol
  2. BPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  3. Cthe string obtained by writing the original symbols in the opposite order
  4. Dtwo strings that can be separated by some continuation leading to different acceptance results
Show Answer
Correct Answer: C. the string obtained by writing the original symbols in the opposite order

Reverse of a string refers to the string obtained by writing the original symbols in the opposite order.

Q24 Formal Languages & Strings

A correct statement about Reverse of a string is:

  1. Aa Turing machine strategy that repeatedly marks matching a's and b's
  2. Bthe problem of deciding whether two finite automata accept exactly the same language
  3. Cthe string obtained by writing the original symbols in the opposite order
  4. Dan operation that means either expression may be chosen
Show Answer
Correct Answer: C. the string obtained by writing the original symbols in the opposite order

Reverse of a string refers to the string obtained by writing the original symbols in the opposite order.

Q25 Formal Languages & Strings

What is meant by Palindrome in Theory of Automata?

  1. Aa grammar in which at most one nonterminal appears at the right end of a production
  2. Ban operation that means either expression may be chosen
  3. Ca string that reads the same from left to right and right to left
  4. Dthe theorem stating that regular expressions and finite automata define the same class of languages
Show Answer
Correct Answer: C. a string that reads the same from left to right and right to left

Palindrome refers to a string that reads the same from left to right and right to left.

Q26 Formal Languages & Strings

Which option best explains Palindrome?

  1. Aa string that reads the same from left to right and right to left
  2. Bthe problem of deciding whether two finite automata accept exactly the same language
  3. Ca necessary property used to prove that some languages are not regular
  4. Da finite automaton that may have zero, one, or multiple possible moves for an input
Show Answer
Correct Answer: A. a string that reads the same from left to right and right to left

Palindrome refers to a string that reads the same from left to right and right to left.

Q27 Formal Languages & Strings

A correct statement about Palindrome is:

  1. Aan abstract computational model with a tape, head, states and transition rules
  2. Ba string that reads the same from left to right and right to left
  3. Ca PDA that guesses the middle of the string and matches the second half using the stack
  4. Da directed labeled graph used to represent language recognition paths
Show Answer
Correct Answer: B. a string that reads the same from left to right and right to left

Palindrome refers to a string that reads the same from left to right and right to left.

Q28 Formal Languages & Strings

What is meant by Language over an alphabet in Theory of Automata?

  1. Aany set of strings formed from the symbols of that alphabet
  2. Ban expression such as (a+b)*ab(a+b)* over {a,b}
  3. Ca property decided by checking whether an accepting state is reachable through a cycle
  4. Da grammar symbol that cannot help derive any terminal string from the start variable
Show Answer
Correct Answer: A. any set of strings formed from the symbols of that alphabet

Language over an alphabet refers to any set of strings formed from the symbols of that alphabet.

Q29 Formal Languages & Strings

Which option best explains Language over an alphabet?

  1. Aany set of strings formed from the symbols of that alphabet
  2. Ba conversion that may split states so outputs become associated with states
  3. Ca finite non-empty set of symbols used to form strings
  4. Dan operation that means either expression may be chosen
Show Answer
Correct Answer: A. any set of strings formed from the symbols of that alphabet

Language over an alphabet refers to any set of strings formed from the symbols of that alphabet.

Q30 Formal Languages & Strings

A correct statement about Language over an alphabet is:

  1. Aan operation that places a symbol on the top of the stack
  2. Ba DFA that toggles between two states whenever symbol a is read
  3. Cany set of strings formed from the symbols of that alphabet
  4. Dthe string obtained by writing the original symbols in the opposite order
Show Answer
Correct Answer: C. any set of strings formed from the symbols of that alphabet

Language over an alphabet refers to any set of strings formed from the symbols of that alphabet.

Q31 Formal Languages & Strings

What is meant by Finite language in Theory of Automata?

  1. Athe classic nonregular language containing equal numbers of a's followed by b's
  2. Ba language that contains only a limited number of strings
  3. Ca string that reads the same from left to right and right to left
  4. Da grammar symbol that cannot help derive any terminal string from the start variable
Show Answer
Correct Answer: B. a language that contains only a limited number of strings

Finite language refers to a language that contains only a limited number of strings.

Q32 Formal Languages & Strings

Which option best explains Finite language?

  1. Aa mathematical machine with finitely many states used to recognize regular languages
  2. Ba finite automaton that may have zero, one, or multiple possible moves for an input
  3. Ca finite automaton equipped with a stack for recognizing context-free languages
  4. Da language that contains only a limited number of strings
Show Answer
Correct Answer: D. a language that contains only a limited number of strings

Finite language refers to a language that contains only a limited number of strings.

Q33 Formal Languages & Strings

A correct statement about Finite language is:

  1. Athe problem of deciding whether a finite automaton accepts at least one string
  2. Ba language that contains only a limited number of strings
  3. Ca formal system of variables, terminals, productions and a start symbol
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: B. a language that contains only a limited number of strings

Finite language refers to a language that contains only a limited number of strings.

Q34 Formal Languages & Strings

What is meant by Infinite language in Theory of Automata?

  1. Aa graph representation of states and labeled transitions
  2. Ba language that contains endlessly many strings
  3. Cthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: B. a language that contains endlessly many strings

Infinite language refers to a language that contains endlessly many strings.

Q35 Formal Languages & Strings

Which option best explains Infinite language?

  1. Aa language that contains endlessly many strings
  2. Ba non-accepting state that the machine cannot escape once entered
  3. Ca snapshot showing current state, unread input and stack contents
  4. Da finite automaton equipped with a stack for recognizing context-free languages
Show Answer
Correct Answer: A. a language that contains endlessly many strings

Infinite language refers to a language that contains endlessly many strings.

Q36 Formal Languages & Strings

A correct statement about Infinite language is:

  1. Aa language that contains endlessly many strings
  2. Bthe string obtained by writing the original symbols in the opposite order
  3. Ca language for which some Turing machine halts on every input and decides membership
  4. Da PDA that guesses the middle of the string and matches the second half using the stack
Show Answer
Correct Answer: A. a language that contains endlessly many strings

Infinite language refers to a language that contains endlessly many strings.

Q37 Formal Languages & Strings

What is meant by Empty language in Theory of Automata?

  1. Aa variable symbol that can be replaced using productions
  2. Ba constant length beyond which strings in an infinite regular language can be decomposed and pumped
  3. Ca language containing no strings at all
  4. Dany set of strings formed from the symbols of that alphabet
Show Answer
Correct Answer: C. a language containing no strings at all

Empty language refers to a language containing no strings at all.

Q38 Formal Languages & Strings

Which option best explains Empty language?

  1. Aan operation that allows zero or more repetitions of a language
  2. Ba property decided by checking whether an accepting state is reachable through a cycle
  3. Ca tabular representation of state changes for each input symbol
  4. Da language containing no strings at all
Show Answer
Correct Answer: D. a language containing no strings at all

Empty language refers to a language containing no strings at all.

Q39 Formal Languages & Strings

A correct statement about Empty language is:

  1. Aa language containing no strings at all
  2. Bthe state from which computation begins
  3. Ca definition that gives base strings and rules for generating more strings
  4. Da prefix notation in which the operator is written before its operands
Show Answer
Correct Answer: A. a language containing no strings at all

Empty language refers to a language containing no strings at all.

Q40 Formal Languages & Strings

What is meant by Recursive definition of a language in Theory of Automata?

  1. Aa grammar with productions restricted to right-linear or left-linear form
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca prefix notation in which the operator is written before its operands
  4. Da definition that gives base strings and rules for generating more strings
Show Answer
Correct Answer: D. a definition that gives base strings and rules for generating more strings

Recursive definition of a language refers to a definition that gives base strings and rules for generating more strings.

Q41 Formal Languages & Strings

Which option best explains Recursive definition of a language?

  1. Aan unbounded memory divided into cells that can hold symbols
  2. Bthe part of a Turing machine that reads, writes and moves on the tape
  3. Ca definition that gives base strings and rules for generating more strings
  4. Da full snapshot of tape contents, head position and current state
Show Answer
Correct Answer: C. a definition that gives base strings and rules for generating more strings

Recursive definition of a language refers to a definition that gives base strings and rules for generating more strings.

Q42 Formal Languages & Strings

A correct statement about Recursive definition of a language is:

  1. Aa definition that gives base strings and rules for generating more strings
  2. Ba symbolic notation used to describe regular languages
  3. Ca CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  4. Da rewriting rule that replaces one symbol or pattern with another string
Show Answer
Correct Answer: A. a definition that gives base strings and rules for generating more strings

Recursive definition of a language refers to a definition that gives base strings and rules for generating more strings.

Q43 Regular Expressions

What is meant by Regular expression in Theory of Automata?

  1. Athe expression (0+1)*, which represents every string over {0,1}
  2. Ba method that creates productions from automaton transitions and final states
  3. Cthe classic nonregular language containing equal numbers of a's followed by b's
  4. Da symbolic notation used to describe regular languages
Show Answer
Correct Answer: D. a symbolic notation used to describe regular languages

Regular expression refers to a symbolic notation used to describe regular languages.

Q44 Regular Expressions

Which option best explains Regular expression?

  1. Athe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  2. Ba finite-state machine whose output depends on the current state and input symbol
  3. Cany set of strings formed from the symbols of that alphabet
  4. Da symbolic notation used to describe regular languages
Show Answer
Correct Answer: D. a symbolic notation used to describe regular languages

Regular expression refers to a symbolic notation used to describe regular languages.

Q45 Regular Expressions

A correct statement about Regular expression is:

  1. Athe part of a Turing machine that reads, writes and moves on the tape
  2. Ba property decided by checking whether an accepting state is reachable through a cycle
  3. Ca symbolic notation used to describe regular languages
  4. Dthe number of symbols occurring in a string
Show Answer
Correct Answer: C. a symbolic notation used to describe regular languages

Regular expression refers to a symbolic notation used to describe regular languages.

Q46 Regular Expressions

What is meant by Union in regular expressions in Theory of Automata?

  1. Aa conversion that may split states so outputs become associated with states
  2. Ba prefix notation in which the operator is written before its operands
  3. Ca mathematical machine with finitely many states used to recognize regular languages
  4. Dan operation that means either expression may be chosen
Show Answer
Correct Answer: D. an operation that means either expression may be chosen

Union in regular expressions refers to an operation that means either expression may be chosen.

Q47 Regular Expressions

Which option best explains Union in regular expressions?

  1. Aan operation that means either expression may be chosen
  2. Ba tree representation showing how a string is derived from a grammar
  3. Ca mathematical machine with finitely many states used to recognize regular languages
  4. Dthe string obtained by writing the original symbols in the opposite order
Show Answer
Correct Answer: A. an operation that means either expression may be chosen

Union in regular expressions refers to an operation that means either expression may be chosen.

Q48 Regular Expressions

A correct statement about Union in regular expressions is:

  1. Aa language that can be recognized by a finite automaton
  2. Ba grammar with productions restricted to right-linear or left-linear form
  3. Ca method that creates automaton states from grammar variables and transitions from productions
  4. Dan operation that means either expression may be chosen
Show Answer
Correct Answer: D. an operation that means either expression may be chosen

Union in regular expressions refers to an operation that means either expression may be chosen.

Q49 Regular Expressions

What is meant by Concatenation in regular expressions in Theory of Automata?

  1. Aan operation that places strings from one language directly after strings from another
  2. Ba tabular representation of state changes for each input symbol
  3. Cthe string obtained by writing the original symbols in the opposite order
  4. Dthe theorem stating that regular expressions and finite automata define the same class of languages
Show Answer
Correct Answer: A. an operation that places strings from one language directly after strings from another

Concatenation in regular expressions refers to an operation that places strings from one language directly after strings from another.

Q50 Regular Expressions

Which option best explains Concatenation in regular expressions?

  1. Athe number of symbols occurring in a string
  2. Bthe string obtained by writing the original symbols in the opposite order
  3. Cthe action of consuming an input symbol while making a transition
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: D. an operation that places strings from one language directly after strings from another

Concatenation in regular expressions refers to an operation that places strings from one language directly after strings from another.

Q51 Regular Expressions

A correct statement about Concatenation in regular expressions is:

  1. Aan operation that places strings from one language directly after strings from another
  2. Ba language that contains only a limited number of strings
  3. Cthe string obtained by writing the original symbols in the opposite order
  4. Da constant length beyond which strings in an infinite regular language can be decomposed and pumped
Show Answer
Correct Answer: A. an operation that places strings from one language directly after strings from another

Concatenation in regular expressions refers to an operation that places strings from one language directly after strings from another.

Q52 Regular Expressions

What is meant by Kleene star in Theory of Automata?

  1. Aa DFA that toggles between two states whenever symbol a is read
  2. Ban operation that allows zero or more repetitions of a language
  3. Ca language generated by some context-free grammar
  4. Da full snapshot of tape contents, head position and current state
Show Answer
Correct Answer: B. an operation that allows zero or more repetitions of a language

Kleene star refers to an operation that allows zero or more repetitions of a language.

Q53 Regular Expressions

Which option best explains Kleene star?

  1. Aan operation that allows zero or more repetitions of a language
  2. Bthe string with length zero, usually denoted by ε or lambda
  3. CPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  4. Dthe action of consuming an input symbol while making a transition
Show Answer
Correct Answer: A. an operation that allows zero or more repetitions of a language

Kleene star refers to an operation that allows zero or more repetitions of a language.

Q54 Regular Expressions

A correct statement about Kleene star is:

  1. Aan operation that allows zero or more repetitions of a language
  2. Bthe rule that tells the automaton which state to move to after reading a symbol
  3. Ca finite automaton that may have zero, one, or multiple possible moves for an input
  4. Da state where the Turing machine stops computation
Show Answer
Correct Answer: A. an operation that allows zero or more repetitions of a language

Kleene star refers to an operation that allows zero or more repetitions of a language.

Q55 Regular Expressions

What is meant by Regular expression for all binary strings in Theory of Automata?

  1. Aa grammar in which every generated string has only one parse tree
  2. Bthe expression (0+1)*, which represents every string over {0,1}
  3. Can operation that places strings from one language directly after strings from another
  4. Da state where the Turing machine stops computation
Show Answer
Correct Answer: B. the expression (0+1)*, which represents every string over {0,1}

Regular expression for all binary strings refers to the expression (0+1)*, which represents every string over {0,1}.

Q56 Regular Expressions

Which option best explains Regular expression for all binary strings?

  1. Aany set of strings formed from the symbols of that alphabet
  2. Ba production of the form A→B where both sides are single variables
  3. Ca natural human language whose meaning may depend on context and everyday usage
  4. Dthe expression (0+1)*, which represents every string over {0,1}
Show Answer
Correct Answer: D. the expression (0+1)*, which represents every string over {0,1}

Regular expression for all binary strings refers to the expression (0+1)*, which represents every string over {0,1}.

Q57 Regular Expressions

A correct statement about Regular expression for all binary strings is:

  1. Athe expression (0+1)*, which represents every string over {0,1}
  2. Bthe classic nonregular language containing equal numbers of a's followed by b's
  3. Cany set of strings formed from the symbols of that alphabet
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: A. the expression (0+1)*, which represents every string over {0,1}

Regular expression for all binary strings refers to the expression (0+1)*, which represents every string over {0,1}.

Q58 Regular Expressions

What is meant by Regular expression for strings ending in 01 in Theory of Automata?

  1. Aan expression such as (0+1)*01 over the alphabet {0,1}
  2. Bthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  3. Ca string that reads the same from left to right and right to left
  4. Da derivation that always replaces the rightmost nonterminal first
Show Answer
Correct Answer: A. an expression such as (0+1)*01 over the alphabet {0,1}

Regular expression for strings ending in 01 refers to an expression such as (0+1)*01 over the alphabet {0,1}.

Q59 Regular Expressions

Which option best explains Regular expression for strings ending in 01?

  1. Aan expression such as (0+1)*01 over the alphabet {0,1}
  2. Ba language for which some Turing machine halts on every input and decides membership
  3. Ca directed labeled graph used to represent language recognition paths
  4. Da property decided by checking whether an accepting state is reachable through a cycle
Show Answer
Correct Answer: A. an expression such as (0+1)*01 over the alphabet {0,1}

Regular expression for strings ending in 01 refers to an expression such as (0+1)*01 over the alphabet {0,1}.

Q60 Regular Expressions

A correct statement about Regular expression for strings ending in 01 is:

  1. Aa definition that gives base strings and rules for generating more strings
  2. Ban expression such as (0+1)*01 over the alphabet {0,1}
  3. Ca rule that writes a symbol, moves the head and changes state
  4. Dan operation that allows zero or more repetitions of a language
Show Answer
Correct Answer: B. an expression such as (0+1)*01 over the alphabet {0,1}

Regular expression for strings ending in 01 refers to an expression such as (0+1)*01 over the alphabet {0,1}.

Q61 Regular Expressions

What is meant by Regular expression for strings starting with a in Theory of Automata?

  1. Aan expression such as a(a+b)* over the alphabet {a,b}
  2. Ba variable that can derive the empty string
  3. Ca finite automaton equipped with a stack for recognizing context-free languages
  4. Dan expression such as (0+1)*01 over the alphabet {0,1}
Show Answer
Correct Answer: A. an expression such as a(a+b)* over the alphabet {a,b}

Regular expression for strings starting with a refers to an expression such as a(a+b)* over the alphabet {a,b}.

Q62 Regular Expressions

Which option best explains Regular expression for strings starting with a?

  1. Athe problem of deciding whether a finite automaton accepts at least one string
  2. Ba rewriting rule that replaces one symbol or pattern with another string
  3. Can expression such as a(a+b)* over the alphabet {a,b}
  4. Dthe rule that tells the automaton which state to move to after reading a symbol
Show Answer
Correct Answer: C. an expression such as a(a+b)* over the alphabet {a,b}

Regular expression for strings starting with a refers to an expression such as a(a+b)* over the alphabet {a,b}.

Q63 Regular Expressions

A correct statement about Regular expression for strings starting with a is:

  1. Aa language that contains endlessly many strings
  2. Ba method that builds a combined automaton using ordered pairs of states
  3. Cthe number of symbols occurring in a string
  4. Dan expression such as a(a+b)* over the alphabet {a,b}
Show Answer
Correct Answer: D. an expression such as a(a+b)* over the alphabet {a,b}

Regular expression for strings starting with a refers to an expression such as a(a+b)* over the alphabet {a,b}.

Q64 Regular Expressions

What is meant by Regular expression for strings containing ab in Theory of Automata?

  1. Aa mathematically defined set of strings over a specified alphabet
  2. Ban expression such as (a+b)*ab(a+b)* over {a,b}
  3. Ca process that removes null, unit and useless productions and converts long rules into binary form
  4. Da variable symbol that can be replaced using productions
Show Answer
Correct Answer: B. an expression such as (a+b)*ab(a+b)* over {a,b}

Regular expression for strings containing ab refers to an expression such as (a+b)*ab(a+b)* over {a,b}.

Q65 Regular Expressions

Which option best explains Regular expression for strings containing ab?

  1. Aa production that derives the empty string
  2. Ban expression such as a(a+b)* over the alphabet {a,b}
  3. Ca grammar in which at most one nonterminal appears at the left end of a production
  4. Dan expression such as (a+b)*ab(a+b)* over {a,b}
Show Answer
Correct Answer: D. an expression such as (a+b)*ab(a+b)* over {a,b}

Regular expression for strings containing ab refers to an expression such as (a+b)*ab(a+b)* over {a,b}.

Q66 Regular Expressions

A correct statement about Regular expression for strings containing ab is:

  1. Aan expression such as (a+b)*ab(a+b)* over {a,b}
  2. Ba symbolic notation used to describe regular languages
  3. Cthe property that a problem has an algorithm that always halts with a yes or no answer
  4. Dany set of strings formed from the symbols of that alphabet
Show Answer
Correct Answer: A. an expression such as (a+b)*ab(a+b)* over {a,b}

Regular expression for strings containing ab refers to an expression such as (a+b)*ab(a+b)* over {a,b}.

Q67 Finite Automata

What is meant by Finite automaton in Theory of Automata?

  1. Aa finite automaton equipped with a stack for recognizing context-free languages
  2. Ba derivation that always replaces the rightmost nonterminal first
  3. Ca mathematical machine with finitely many states used to recognize regular languages
  4. Dthe action of consuming an input symbol while making a transition
Show Answer
Correct Answer: C. a mathematical machine with finitely many states used to recognize regular languages

Finite automaton refers to a mathematical machine with finitely many states used to recognize regular languages.

Q68 Finite Automata

Which option best explains Finite automaton?

  1. Aa derivation that always replaces the leftmost nonterminal first
  2. Ba mathematical machine with finitely many states used to recognize regular languages
  3. Ca formal system of variables, terminals, productions and a start symbol
  4. Dthe string with length zero, usually denoted by ε or lambda
Show Answer
Correct Answer: B. a mathematical machine with finitely many states used to recognize regular languages

Finite automaton refers to a mathematical machine with finitely many states used to recognize regular languages.

Q69 Finite Automata

A correct statement about Finite automaton is:

  1. Aa mathematical machine with finitely many states used to recognize regular languages
  2. Ba state where the Turing machine stops computation
  3. Cthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  4. Da Turing machine strategy that repeatedly marks matching a's and b's
Show Answer
Correct Answer: A. a mathematical machine with finitely many states used to recognize regular languages

Finite automaton refers to a mathematical machine with finitely many states used to recognize regular languages.

Q70 Finite Automata

What is meant by Deterministic finite automaton in Theory of Automata?

  1. Aa finite automaton with exactly one next state for each state and input symbol
  2. Ban expression such as (0+1)*01 over the alphabet {0,1}
  3. Ca PDA that pushes symbols for a's and pops them while reading b's
  4. Da variable that can derive the empty string
Show Answer
Correct Answer: A. a finite automaton with exactly one next state for each state and input symbol

Deterministic finite automaton refers to a finite automaton with exactly one next state for each state and input symbol.

Q71 Finite Automata

Which option best explains Deterministic finite automaton?

  1. Aa finite automaton with exactly one next state for each state and input symbol
  2. Ba prefix notation in which the operator is written before its operands
  3. Can alphabet whose symbols are clearly defined and can be used to build strings
  4. Da mathematical machine with finitely many states used to recognize regular languages
Show Answer
Correct Answer: A. a finite automaton with exactly one next state for each state and input symbol

Deterministic finite automaton refers to a finite automaton with exactly one next state for each state and input symbol.

Q72 Finite Automata

A correct statement about Deterministic finite automaton is:

  1. Aa problem whose answer is either yes or no
  2. Ba finite automaton with exactly one next state for each state and input symbol
  3. Can expression such as a(a+b)* over the alphabet {a,b}
  4. Da move that changes state without consuming an input symbol
Show Answer
Correct Answer: B. a finite automaton with exactly one next state for each state and input symbol

Deterministic finite automaton refers to a finite automaton with exactly one next state for each state and input symbol.

Q73 Finite Automata

What is meant by State in finite automata in Theory of Automata?

  1. Aa finite-state machine whose output depends only on the current state
  2. Ba state that causes a string to be accepted when input processing ends there
  3. Ca graph representation of states and labeled transitions
  4. Da named condition or memory position of the machine
Show Answer
Correct Answer: D. a named condition or memory position of the machine

State in finite automata refers to a named condition or memory position of the machine.

Q74 Finite Automata

Which option best explains State in finite automata?

  1. Aa non-accepting state that the machine cannot escape once entered
  2. Ban alphabet whose symbols are clearly defined and can be used to build strings
  3. Ca named condition or memory position of the machine
  4. Da graph representation of states and labeled transitions
Show Answer
Correct Answer: C. a named condition or memory position of the machine

State in finite automata refers to a named condition or memory position of the machine.

Q75 Finite Automata

A correct statement about State in finite automata is:

  1. Athe method of converting an NFA into an equivalent DFA using sets of NFA states
  2. Ba named condition or memory position of the machine
  3. Ca string that reads the same from left to right and right to left
  4. Da process that removes null, unit and useless productions and converts long rules into binary form
Show Answer
Correct Answer: B. a named condition or memory position of the machine

State in finite automata refers to a named condition or memory position of the machine.

Q76 Finite Automata

What is meant by Start state in Theory of Automata?

  1. Aa variable symbol that can be replaced using productions
  2. Bthe classic nonregular language containing equal numbers of a's followed by b's
  3. Cthe state from which computation begins
  4. Da full snapshot of tape contents, head position and current state
Show Answer
Correct Answer: C. the state from which computation begins

Start state refers to the state from which computation begins.

Q77 Finite Automata

Which option best explains Start state?

  1. Aa finite automaton that may have zero, one, or multiple possible moves for an input
  2. Bthe action of consuming an input symbol while making a transition
  3. Cthe state from which computation begins
  4. Da mathematical machine with finitely many states used to recognize regular languages
Show Answer
Correct Answer: C. the state from which computation begins

Start state refers to the state from which computation begins.

Q78 Finite Automata

A correct statement about Start state is:

  1. Aa CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  2. Bthe distinguished nonterminal from which derivation begins
  3. Ca grammar whose productions have a single nonterminal on the left side
  4. Dthe state from which computation begins
Show Answer
Correct Answer: D. the state from which computation begins

Start state refers to the state from which computation begins.

Q79 Finite Automata

What is meant by Final state in Theory of Automata?

  1. Aa state that causes a string to be accepted when input processing ends there
  2. Ban operation that removes the top symbol from the stack
  3. Cthe property of a grammar that allows a string to have more than one parse tree or derivation
  4. Da named condition or memory position of the machine
Show Answer
Correct Answer: A. a state that causes a string to be accepted when input processing ends there

Final state refers to a state that causes a string to be accepted when input processing ends there.

Q80 Finite Automata

Which option best explains Final state?

  1. Aa mathematically defined set of strings over a specified alphabet
  2. Bthe classic nonregular language containing equal numbers of a's followed by b's
  3. Ca state that causes a string to be accepted when input processing ends there
  4. Da characterization of regular languages using finitely many equivalence classes of distinguishable strings
Show Answer
Correct Answer: C. a state that causes a string to be accepted when input processing ends there

Final state refers to a state that causes a string to be accepted when input processing ends there.

Q81 Finite Automata

A correct statement about Final state is:

  1. Aa state where the Turing machine stops computation
  2. Ba string that reads the same from left to right and right to left
  3. Ca state that causes a string to be accepted when input processing ends there
  4. Da variable symbol that can be replaced using productions
Show Answer
Correct Answer: C. a state that causes a string to be accepted when input processing ends there

Final state refers to a state that causes a string to be accepted when input processing ends there.

Q82 Finite Automata

What is meant by Transition function in Theory of Automata?

  1. Athe problem of deciding whether two finite automata accept exactly the same language
  2. Ba directed labeled graph used to represent language recognition paths
  3. Cthe rule that tells the automaton which state to move to after reading a symbol
  4. Da necessary property used to prove that some languages are not regular
Show Answer
Correct Answer: C. the rule that tells the automaton which state to move to after reading a symbol

Transition function refers to the rule that tells the automaton which state to move to after reading a symbol.

Q83 Finite Automata

Which option best explains Transition function?

  1. Aa language generated by some context-free grammar
  2. Ba symbol that appears in final strings of the language
  3. Cthe rule that tells the automaton which state to move to after reading a symbol
  4. Da problem whose answer is either yes or no
Show Answer
Correct Answer: C. the rule that tells the automaton which state to move to after reading a symbol

Transition function refers to the rule that tells the automaton which state to move to after reading a symbol.

Q84 Finite Automata

A correct statement about Transition function is:

  1. Aa postfix notation in which the operator is written after its operands
  2. Ba named condition or memory position of the machine
  3. Ca state where the Turing machine stops computation
  4. Dthe rule that tells the automaton which state to move to after reading a symbol
Show Answer
Correct Answer: D. the rule that tells the automaton which state to move to after reading a symbol

Transition function refers to the rule that tells the automaton which state to move to after reading a symbol.

Q85 Finite Automata

What is meant by Transition table in Theory of Automata?

  1. Aan operation that places a symbol on the top of the stack
  2. Bthe ability of a PDA to choose among multiple valid transitions
  3. Ca directed labeled graph used to represent language recognition paths
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: D. a tabular representation of state changes for each input symbol

Transition table refers to a tabular representation of state changes for each input symbol.

Q86 Finite Automata

Which option best explains Transition table?

  1. Aa directed labeled graph used to represent language recognition paths
  2. Ba language that can be recognized by a finite automaton
  3. Ca state that causes a string to be accepted when input processing ends there
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: D. a tabular representation of state changes for each input symbol

Transition table refers to a tabular representation of state changes for each input symbol.

Q87 Finite Automata

A correct statement about Transition table is:

  1. Aa finite-state machine whose output depends on the current state and input symbol
  2. Ba tabular representation of state changes for each input symbol
  3. Ca full snapshot of tape contents, head position and current state
  4. Da grammar in which at most one nonterminal appears at the left end of a production
Show Answer
Correct Answer: B. a tabular representation of state changes for each input symbol

Transition table refers to a tabular representation of state changes for each input symbol.

Q88 Finite Automata

What is meant by Transition diagram in Theory of Automata?

  1. Aa graph representation of states and labeled transitions
  2. Ba rule that writes a symbol, moves the head and changes state
  3. Can expression such as (a+b)*ab(a+b)* over {a,b}
  4. Da production that derives the empty string
Show Answer
Correct Answer: A. a graph representation of states and labeled transitions

Transition diagram refers to a graph representation of states and labeled transitions.

Q89 Finite Automata

Which option best explains Transition diagram?

  1. Aa production of the form A→B where both sides are single variables
  2. Ba graph representation of states and labeled transitions
  3. Ca language that contains endlessly many strings
  4. Da DFA that toggles between two states whenever symbol a is read
Show Answer
Correct Answer: B. a graph representation of states and labeled transitions

Transition diagram refers to a graph representation of states and labeled transitions.

Q90 Finite Automata

A correct statement about Transition diagram is:

  1. Athe string with length zero, usually denoted by ε or lambda
  2. Bthe expression (0+1)*, which represents every string over {0,1}
  3. Ca graph representation of states and labeled transitions
  4. Dan alphabet whose symbols are clearly defined and can be used to build strings
Show Answer
Correct Answer: C. a graph representation of states and labeled transitions

Transition diagram refers to a graph representation of states and labeled transitions.

Q91 Finite Automata

What is meant by Trap state in Theory of Automata?

  1. Aa method that creates automaton states from grammar variables and transitions from productions
  2. Ba non-accepting state that the machine cannot escape once entered
  3. Ca PDA that guesses the middle of the string and matches the second half using the stack
  4. Da postfix notation in which the operator is written after its operands
Show Answer
Correct Answer: B. a non-accepting state that the machine cannot escape once entered

Trap state refers to a non-accepting state that the machine cannot escape once entered.

Q92 Finite Automata

Which option best explains Trap state?

  1. Aa non-accepting state that the machine cannot escape once entered
  2. Ba language that cannot be recognized by any finite automaton
  3. Cthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: A. a non-accepting state that the machine cannot escape once entered

Trap state refers to a non-accepting state that the machine cannot escape once entered.

Q93 Finite Automata

A correct statement about Trap state is:

  1. Aa process that removes null, unit and useless productions and converts long rules into binary form
  2. Ba definition that gives base strings and rules for generating more strings
  3. Ca production of the form A→B where both sides are single variables
  4. Da non-accepting state that the machine cannot escape once entered
Show Answer
Correct Answer: D. a non-accepting state that the machine cannot escape once entered

Trap state refers to a non-accepting state that the machine cannot escape once entered.

Q94 Finite Automata

What is meant by DFA for even number of a's in Theory of Automata?

  1. Aa characterization of regular languages using finitely many equivalence classes of distinguishable strings
  2. Ba DFA that toggles between two states whenever symbol a is read
  3. Ca finite-state machine whose output depends on the current state and input symbol
  4. Da problem whose answer is either yes or no
Show Answer
Correct Answer: B. a DFA that toggles between two states whenever symbol a is read

DFA for even number of a's refers to a DFA that toggles between two states whenever symbol a is read.

Q95 Finite Automata

Which option best explains DFA for even number of a's?

  1. Aan operation that means either expression may be chosen
  2. Ba method that creates automaton states from grammar variables and transitions from productions
  3. Can operation that allows zero or more repetitions of a language
  4. Da DFA that toggles between two states whenever symbol a is read
Show Answer
Correct Answer: D. a DFA that toggles between two states whenever symbol a is read

DFA for even number of a's refers to a DFA that toggles between two states whenever symbol a is read.

Q96 Finite Automata

A correct statement about DFA for even number of a's is:

  1. Aa production of the form A→B where both sides are single variables
  2. Ba grammar in which at most one nonterminal appears at the left end of a production
  3. Cthe ability of a PDA to choose among multiple valid transitions
  4. Da DFA that toggles between two states whenever symbol a is read
Show Answer
Correct Answer: D. a DFA that toggles between two states whenever symbol a is read

DFA for even number of a's refers to a DFA that toggles between two states whenever symbol a is read.

Q97 Finite Automata

What is meant by DFA complement in Theory of Automata?

  1. Aa finite-state machine whose output depends only on the current state
  2. Ban expression such as a(a+b)* over the alphabet {a,b}
  3. Ca variable that can derive the empty string
  4. Dthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
Show Answer
Correct Answer: D. the language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA

DFA complement refers to the language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA.

Q98 Finite Automata

Which option best explains DFA complement?

  1. Athe method of converting an NFA into an equivalent DFA using sets of NFA states
  2. Ban abstract computational model with a tape, head, states and transition rules
  3. Ca process that removes null, unit and useless productions and converts long rules into binary form
  4. Dthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
Show Answer
Correct Answer: D. the language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA

DFA complement refers to the language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA.

Q99 Finite Automata

A correct statement about DFA complement is:

  1. Athe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  2. Ba grammar in which at most one nonterminal appears at the left end of a production
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. Dany set of strings formed from the symbols of that alphabet
Show Answer
Correct Answer: A. the language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA

DFA complement refers to the language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA.

Q100 Finite Automata

What is meant by Product construction in Theory of Automata?

  1. Aa grammar whose productions have a single nonterminal on the left side
  2. Ba property decided by checking whether an accepting state is reachable through a cycle
  3. Ca method that builds a combined automaton using ordered pairs of states
  4. Da variable symbol that can be replaced using productions
Show Answer
Correct Answer: C. a method that builds a combined automaton using ordered pairs of states

Product construction refers to a method that builds a combined automaton using ordered pairs of states.

Q101 Finite Automata

Which option best explains Product construction?

  1. Aa method that builds a combined automaton using ordered pairs of states
  2. Ba graph representation of states and labeled transitions
  3. Cthe property that a problem has an algorithm that always halts with a yes or no answer
  4. Dthe property of a grammar that allows a string to have more than one parse tree or derivation
Show Answer
Correct Answer: A. a method that builds a combined automaton using ordered pairs of states

Product construction refers to a method that builds a combined automaton using ordered pairs of states.

Q102 Finite Automata

A correct statement about Product construction is:

  1. Aa string that reads the same from left to right and right to left
  2. Ba postfix notation in which the operator is written after its operands
  3. Ca method that builds a combined automaton using ordered pairs of states
  4. Da prefix notation in which the operator is written before its operands
Show Answer
Correct Answer: C. a method that builds a combined automaton using ordered pairs of states

Product construction refers to a method that builds a combined automaton using ordered pairs of states.

Q103 Finite Automata

What is meant by Nondeterministic finite automaton in Theory of Automata?

  1. Aa state that causes a string to be accepted when input processing ends there
  2. Ba postfix notation in which the operator is written after its operands
  3. Cthe string obtained by writing the original symbols in the opposite order
  4. Da finite automaton that may have zero, one, or multiple possible moves for an input
Show Answer
Correct Answer: D. a finite automaton that may have zero, one, or multiple possible moves for an input

Nondeterministic finite automaton refers to a finite automaton that may have zero, one, or multiple possible moves for an input.

Q104 Finite Automata

Which option best explains Nondeterministic finite automaton?

  1. Aa tree representation showing how a string is derived from a grammar
  2. Ban operation that removes the top symbol from the stack
  3. Ca grammar symbol that cannot help derive any terminal string from the start variable
  4. Da finite automaton that may have zero, one, or multiple possible moves for an input
Show Answer
Correct Answer: D. a finite automaton that may have zero, one, or multiple possible moves for an input

Nondeterministic finite automaton refers to a finite automaton that may have zero, one, or multiple possible moves for an input.

Q105 Finite Automata

A correct statement about Nondeterministic finite automaton is:

  1. Aa production of the form A→B where both sides are single variables
  2. Ba directed labeled graph used to represent language recognition paths
  3. Cthe property of a grammar that allows a string to have more than one parse tree or derivation
  4. Da finite automaton that may have zero, one, or multiple possible moves for an input
Show Answer
Correct Answer: D. a finite automaton that may have zero, one, or multiple possible moves for an input

Nondeterministic finite automaton refers to a finite automaton that may have zero, one, or multiple possible moves for an input.

Q106 Finite Automata

What is meant by Epsilon transition in Theory of Automata?

  1. Aa finite automaton that may have zero, one, or multiple possible moves for an input
  2. Ba conversion that may split states so outputs become associated with states
  3. Ca tabular representation of state changes for each input symbol
  4. Da move that changes state without consuming an input symbol
Show Answer
Correct Answer: D. a move that changes state without consuming an input symbol

Epsilon transition refers to a move that changes state without consuming an input symbol.

Q107 Finite Automata

Which option best explains Epsilon transition?

  1. Aa rewriting rule that replaces one symbol or pattern with another string
  2. Bthe property of a grammar that allows a string to have more than one parse tree or derivation
  3. Ca state where the Turing machine stops computation
  4. Da move that changes state without consuming an input symbol
Show Answer
Correct Answer: D. a move that changes state without consuming an input symbol

Epsilon transition refers to a move that changes state without consuming an input symbol.

Q108 Finite Automata

A correct statement about Epsilon transition is:

  1. Aa PDA that pushes symbols for a's and pops them while reading b's
  2. Ba move that changes state without consuming an input symbol
  3. Can operation that places strings from one language directly after strings from another
  4. Da finite-state machine whose output depends on the current state and input symbol
Show Answer
Correct Answer: B. a move that changes state without consuming an input symbol

Epsilon transition refers to a move that changes state without consuming an input symbol.

Q109 Finite Automata

What is meant by Subset construction in Theory of Automata?

  1. Aa grammar with productions restricted to right-linear or left-linear form
  2. Ba language that contains only a limited number of strings
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. Dan unbounded memory divided into cells that can hold symbols
Show Answer
Correct Answer: C. the method of converting an NFA into an equivalent DFA using sets of NFA states

Subset construction refers to the method of converting an NFA into an equivalent DFA using sets of NFA states.

Q110 Finite Automata

Which option best explains Subset construction?

  1. Athe method of converting an NFA into an equivalent DFA using sets of NFA states
  2. Ba method that builds a combined automaton using ordered pairs of states
  3. Cthe number of symbols occurring in a string
  4. Da tree representation showing how a string is derived from a grammar
Show Answer
Correct Answer: A. the method of converting an NFA into an equivalent DFA using sets of NFA states

Subset construction refers to the method of converting an NFA into an equivalent DFA using sets of NFA states.

Q111 Finite Automata

A correct statement about Subset construction is:

  1. Aa symbol that appears in final strings of the language
  2. Ba grammar symbol that cannot help derive any terminal string from the start variable
  3. Ca rewriting rule that replaces one symbol or pattern with another string
  4. Dthe method of converting an NFA into an equivalent DFA using sets of NFA states
Show Answer
Correct Answer: D. the method of converting an NFA into an equivalent DFA using sets of NFA states

Subset construction refers to the method of converting an NFA into an equivalent DFA using sets of NFA states.

Q112 Finite Automata

What is meant by Regular language in Theory of Automata?

  1. Aa language that contains only a limited number of strings
  2. Ba language that can be recognized by a finite automaton
  3. Ca finite-state machine whose output depends only on the current state
  4. Dthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
Show Answer
Correct Answer: B. a language that can be recognized by a finite automaton

Regular language refers to a language that can be recognized by a finite automaton.

Q113 Finite Automata

Which option best explains Regular language?

  1. Aa tabular representation of state changes for each input symbol
  2. Ba language that can be recognized by a finite automaton
  3. Cthe part of a Turing machine that reads, writes and moves on the tape
  4. Dthe distinguished nonterminal from which derivation begins
Show Answer
Correct Answer: B. a language that can be recognized by a finite automaton

Regular language refers to a language that can be recognized by a finite automaton.

Q114 Finite Automata

A correct statement about Regular language is:

  1. Aa language that can be recognized by a finite automaton
  2. Ba DFA that toggles between two states whenever symbol a is read
  3. Ca production of the form A→B where both sides are single variables
  4. Dan alphabet whose symbols are clearly defined and can be used to build strings
Show Answer
Correct Answer: A. a language that can be recognized by a finite automaton

Regular language refers to a language that can be recognized by a finite automaton.

Q115 Finite Automata

What is meant by Kleene theorem in Theory of Automata?

  1. Aan operation that places strings from one language directly after strings from another
  2. Bthe theorem stating that regular expressions and finite automata define the same class of languages
  3. Ca finite-state machine whose output depends only on the current state
  4. Da non-accepting state that the machine cannot escape once entered
Show Answer
Correct Answer: B. the theorem stating that regular expressions and finite automata define the same class of languages

Kleene theorem refers to the theorem stating that regular expressions and finite automata define the same class of languages.

Q116 Finite Automata

Which option best explains Kleene theorem?

  1. Aa problem whose answer is either yes or no
  2. Bthe theorem stating that regular expressions and finite automata define the same class of languages
  3. Ca finite-state machine whose output depends on the current state and input symbol
  4. Dthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
Show Answer
Correct Answer: B. the theorem stating that regular expressions and finite automata define the same class of languages

Kleene theorem refers to the theorem stating that regular expressions and finite automata define the same class of languages.

Q117 Finite Automata

A correct statement about Kleene theorem is:

  1. Athe theorem stating that regular expressions and finite automata define the same class of languages
  2. Ba definition that gives base strings and rules for generating more strings
  3. Ca formal system of variables, terminals, productions and a start symbol
  4. Dan expression such as a(a+b)* over the alphabet {a,b}
Show Answer
Correct Answer: A. the theorem stating that regular expressions and finite automata define the same class of languages

Kleene theorem refers to the theorem stating that regular expressions and finite automata define the same class of languages.

Q118 Finite Automata

What is meant by Transition graph in Theory of Automata?

  1. Athe problem of deciding whether a finite automaton accepts at least one string
  2. Ba directed labeled graph used to represent language recognition paths
  3. Cthe state from which computation begins
  4. Da grammar in which every generated string has only one parse tree
Show Answer
Correct Answer: B. a directed labeled graph used to represent language recognition paths

Transition graph refers to a directed labeled graph used to represent language recognition paths.

Q119 Finite Automata

Which option best explains Transition graph?

  1. Aa problem whose answer is either yes or no
  2. Ba definition that gives base strings and rules for generating more strings
  3. Ca directed labeled graph used to represent language recognition paths
  4. Da process that removes null, unit and useless productions and converts long rules into binary form
Show Answer
Correct Answer: C. a directed labeled graph used to represent language recognition paths

Transition graph refers to a directed labeled graph used to represent language recognition paths.

Q120 Finite Automata

A correct statement about Transition graph is:

  1. Aan operation that places a symbol on the top of the stack
  2. Bthe string with length zero, usually denoted by ε or lambda
  3. Cthe distinguished nonterminal from which derivation begins
  4. Da directed labeled graph used to represent language recognition paths
Show Answer
Correct Answer: D. a directed labeled graph used to represent language recognition paths

Transition graph refers to a directed labeled graph used to represent language recognition paths.

Q121 Grammars & Derivations

What is meant by Grammar in Theory of Automata?

  1. Aa formal system of variables, terminals, productions and a start symbol
  2. Ba necessary property used to prove that some languages are not regular
  3. Ca string that reads the same from left to right and right to left
  4. Dan unbounded memory divided into cells that can hold symbols
Show Answer
Correct Answer: A. a formal system of variables, terminals, productions and a start symbol

Grammar refers to a formal system of variables, terminals, productions and a start symbol.

Q122 Grammars & Derivations

Which option best explains Grammar?

  1. Aa conversion that may split states so outputs become associated with states
  2. Ba definition that gives base strings and rules for generating more strings
  3. Ca formal system of variables, terminals, productions and a start symbol
  4. Da grammar in which at most one nonterminal appears at the right end of a production
Show Answer
Correct Answer: C. a formal system of variables, terminals, productions and a start symbol

Grammar refers to a formal system of variables, terminals, productions and a start symbol.

Q123 Grammars & Derivations

A correct statement about Grammar is:

  1. Aa language for which some Turing machine halts on every input and decides membership
  2. Ba formal system of variables, terminals, productions and a start symbol
  3. Ca grammar in which at most one nonterminal appears at the right end of a production
  4. Dan expression such as (0+1)*01 over the alphabet {0,1}
Show Answer
Correct Answer: B. a formal system of variables, terminals, productions and a start symbol

Grammar refers to a formal system of variables, terminals, productions and a start symbol.

Q124 Grammars & Derivations

What is meant by Context-free grammar in Theory of Automata?

  1. Athe ability of a PDA to choose among multiple valid transitions
  2. Ba conversion that labels each incoming transition with the output of its destination state
  3. Cthe classic nonregular language containing equal numbers of a's followed by b's
  4. Da grammar whose productions have a single nonterminal on the left side
Show Answer
Correct Answer: D. a grammar whose productions have a single nonterminal on the left side

Context-free grammar refers to a grammar whose productions have a single nonterminal on the left side.

Q125 Grammars & Derivations

Which option best explains Context-free grammar?

  1. Aa grammar whose productions have a single nonterminal on the left side
  2. Ba symbol that appears in final strings of the language
  3. Ca DFA that toggles between two states whenever symbol a is read
  4. Da language that contains endlessly many strings
Show Answer
Correct Answer: A. a grammar whose productions have a single nonterminal on the left side

Context-free grammar refers to a grammar whose productions have a single nonterminal on the left side.

Q126 Grammars & Derivations

A correct statement about Context-free grammar is:

  1. Aan operation that places a symbol on the top of the stack
  2. Ba production of the form A→B where both sides are single variables
  3. Ca finite-state machine whose output depends on the current state and input symbol
  4. Da grammar whose productions have a single nonterminal on the left side
Show Answer
Correct Answer: D. a grammar whose productions have a single nonterminal on the left side

Context-free grammar refers to a grammar whose productions have a single nonterminal on the left side.

Q127 Grammars & Derivations

What is meant by Terminal symbol in Theory of Automata?

  1. Aa finite automaton with exactly one next state for each state and input symbol
  2. Ba grammar whose productions have a single nonterminal on the left side
  3. Ca language that cannot be recognized by any finite automaton
  4. Da symbol that appears in final strings of the language
Show Answer
Correct Answer: D. a symbol that appears in final strings of the language

Terminal symbol refers to a symbol that appears in final strings of the language.

Q128 Grammars & Derivations

Which option best explains Terminal symbol?

  1. Aa rewriting rule that replaces one symbol or pattern with another string
  2. Ba method that builds a combined automaton using ordered pairs of states
  3. Ca symbol that appears in final strings of the language
  4. Da move that changes state without consuming an input symbol
Show Answer
Correct Answer: C. a symbol that appears in final strings of the language

Terminal symbol refers to a symbol that appears in final strings of the language.

Q129 Grammars & Derivations

A correct statement about Terminal symbol is:

  1. Aa characterization of regular languages using finitely many equivalence classes of distinguishable strings
  2. Ba symbol that appears in final strings of the language
  3. Ca language that contains only a limited number of strings
  4. Da named condition or memory position of the machine
Show Answer
Correct Answer: B. a symbol that appears in final strings of the language

Terminal symbol refers to a symbol that appears in final strings of the language.

Q130 Grammars & Derivations

What is meant by Nonterminal symbol in Theory of Automata?

  1. Aa conversion that may split states so outputs become associated with states
  2. Ba variable symbol that can be replaced using productions
  3. Ca grammar symbol that cannot help derive any terminal string from the start variable
  4. Da last-in first-out memory structure used by a pushdown automaton
Show Answer
Correct Answer: B. a variable symbol that can be replaced using productions

Nonterminal symbol refers to a variable symbol that can be replaced using productions.

Q131 Grammars & Derivations

Which option best explains Nonterminal symbol?

  1. Athe problem of deciding whether a finite automaton accepts at least one string
  2. Ba conversion that may split states so outputs become associated with states
  3. Can unbounded memory divided into cells that can hold symbols
  4. Da variable symbol that can be replaced using productions
Show Answer
Correct Answer: D. a variable symbol that can be replaced using productions

Nonterminal symbol refers to a variable symbol that can be replaced using productions.

Q132 Grammars & Derivations

A correct statement about Nonterminal symbol is:

  1. Aa language that can be recognized by a finite automaton
  2. Ba language generated by some context-free grammar
  3. Ca variable symbol that can be replaced using productions
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: C. a variable symbol that can be replaced using productions

Nonterminal symbol refers to a variable symbol that can be replaced using productions.

Q133 Grammars & Derivations

What is meant by Production rule in Theory of Automata?

  1. Aa finite-state machine whose output depends only on the current state
  2. Ba rewriting rule that replaces one symbol or pattern with another string
  3. Ca finite automaton equipped with a stack for recognizing context-free languages
  4. Dtwo strings that can be separated by some continuation leading to different acceptance results
Show Answer
Correct Answer: B. a rewriting rule that replaces one symbol or pattern with another string

Production rule refers to a rewriting rule that replaces one symbol or pattern with another string.

Q134 Grammars & Derivations

Which option best explains Production rule?

  1. Aany string of terminals and nonterminals produced during a derivation
  2. Ba rewriting rule that replaces one symbol or pattern with another string
  3. Ca problem whose answer is either yes or no
  4. Da method that creates automaton states from grammar variables and transitions from productions
Show Answer
Correct Answer: B. a rewriting rule that replaces one symbol or pattern with another string

Production rule refers to a rewriting rule that replaces one symbol or pattern with another string.

Q135 Grammars & Derivations

A correct statement about Production rule is:

  1. Athe problem of deciding whether two finite automata accept exactly the same language
  2. Ba graph representation of states and labeled transitions
  3. Ca rewriting rule that replaces one symbol or pattern with another string
  4. Dan operation that means either expression may be chosen
Show Answer
Correct Answer: C. a rewriting rule that replaces one symbol or pattern with another string

Production rule refers to a rewriting rule that replaces one symbol or pattern with another string.

Q136 Grammars & Derivations

What is meant by Start variable in Theory of Automata?

  1. Athe distinguished nonterminal from which derivation begins
  2. Ba grammar symbol that cannot help derive any terminal string from the start variable
  3. Ca variable that can derive the empty string
  4. Dthe classic nonregular language containing equal numbers of a's followed by b's
Show Answer
Correct Answer: A. the distinguished nonterminal from which derivation begins

Start variable refers to the distinguished nonterminal from which derivation begins.

Q137 Grammars & Derivations

Which option best explains Start variable?

  1. Aa conversion that labels each incoming transition with the output of its destination state
  2. Bthe distinguished nonterminal from which derivation begins
  3. Ca production that derives the empty string
  4. Da move that changes state without consuming an input symbol
Show Answer
Correct Answer: B. the distinguished nonterminal from which derivation begins

Start variable refers to the distinguished nonterminal from which derivation begins.

Q138 Grammars & Derivations

A correct statement about Start variable is:

  1. Aa derivation that always replaces the leftmost nonterminal first
  2. Ba language that can be recognized by a finite automaton
  3. Cthe distinguished nonterminal from which derivation begins
  4. Da graph representation of states and labeled transitions
Show Answer
Correct Answer: C. the distinguished nonterminal from which derivation begins

Start variable refers to the distinguished nonterminal from which derivation begins.

Q139 Grammars & Derivations

What is meant by Sentential form in Theory of Automata?

  1. Athe classic nonregular language containing equal numbers of a's followed by b's
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca language for which some Turing machine halts on every input and decides membership
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: B. any string of terminals and nonterminals produced during a derivation

Sentential form refers to any string of terminals and nonterminals produced during a derivation.

Q140 Grammars & Derivations

Which option best explains Sentential form?

  1. Aa finite automaton equipped with a stack for recognizing context-free languages
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca problem whose answer is either yes or no
  4. Da language that can be recognized by a finite automaton
Show Answer
Correct Answer: B. any string of terminals and nonterminals produced during a derivation

Sentential form refers to any string of terminals and nonterminals produced during a derivation.

Q141 Grammars & Derivations

A correct statement about Sentential form is:

  1. Aa definition that gives base strings and rules for generating more strings
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca natural human language whose meaning may depend on context and everyday usage
  4. Dan operation that removes the top symbol from the stack
Show Answer
Correct Answer: B. any string of terminals and nonterminals produced during a derivation

Sentential form refers to any string of terminals and nonterminals produced during a derivation.

Q142 Grammars & Derivations

What is meant by Leftmost derivation in Theory of Automata?

  1. Aa derivation that always replaces the leftmost nonterminal first
  2. Ba finite automaton with exactly one next state for each state and input symbol
  3. Ca variable symbol that can be replaced using productions
  4. Da grammar in which at most one nonterminal appears at the left end of a production
Show Answer
Correct Answer: A. a derivation that always replaces the leftmost nonterminal first

Leftmost derivation refers to a derivation that always replaces the leftmost nonterminal first.

Q143 Grammars & Derivations

Which option best explains Leftmost derivation?

  1. Aa string that reads the same from left to right and right to left
  2. Ba language generated by some context-free grammar
  3. Ca symbolic notation used to describe regular languages
  4. Da derivation that always replaces the leftmost nonterminal first
Show Answer
Correct Answer: D. a derivation that always replaces the leftmost nonterminal first

Leftmost derivation refers to a derivation that always replaces the leftmost nonterminal first.

Q144 Grammars & Derivations

A correct statement about Leftmost derivation is:

  1. Aan operation that places a symbol on the top of the stack
  2. Bthe theorem stating that regular expressions and finite automata define the same class of languages
  3. Ca derivation that always replaces the leftmost nonterminal first
  4. Dan expression such as (0+1)*01 over the alphabet {0,1}
Show Answer
Correct Answer: C. a derivation that always replaces the leftmost nonterminal first

Leftmost derivation refers to a derivation that always replaces the leftmost nonterminal first.

Q145 Grammars & Derivations

What is meant by Rightmost derivation in Theory of Automata?

  1. Aa last-in first-out memory structure used by a pushdown automaton
  2. Ba derivation that always replaces the rightmost nonterminal first
  3. Ca postfix notation in which the operator is written after its operands
  4. Da grammar symbol that cannot help derive any terminal string from the start variable
Show Answer
Correct Answer: B. a derivation that always replaces the rightmost nonterminal first

Rightmost derivation refers to a derivation that always replaces the rightmost nonterminal first.

Q146 Grammars & Derivations

Which option best explains Rightmost derivation?

  1. Athe theorem stating that regular expressions and finite automata define the same class of languages
  2. Ba method that creates productions from automaton transitions and final states
  3. Ca grammar in which at most one nonterminal appears at the left end of a production
  4. Da derivation that always replaces the rightmost nonterminal first
Show Answer
Correct Answer: D. a derivation that always replaces the rightmost nonterminal first

Rightmost derivation refers to a derivation that always replaces the rightmost nonterminal first.

Q147 Grammars & Derivations

A correct statement about Rightmost derivation is:

  1. Aa derivation that always replaces the rightmost nonterminal first
  2. Bthe ability of a PDA to choose among multiple valid transitions
  3. Ca language containing no strings at all
  4. Da production that derives the empty string
Show Answer
Correct Answer: A. a derivation that always replaces the rightmost nonterminal first

Rightmost derivation refers to a derivation that always replaces the rightmost nonterminal first.

Q148 Grammars & Derivations

What is meant by Parse tree in Theory of Automata?

  1. Aa tree representation showing how a string is derived from a grammar
  2. Ba language that contains only a limited number of strings
  3. Ca method that builds a combined automaton using ordered pairs of states
  4. Da rule that writes a symbol, moves the head and changes state
Show Answer
Correct Answer: A. a tree representation showing how a string is derived from a grammar

Parse tree refers to a tree representation showing how a string is derived from a grammar.

Q149 Grammars & Derivations

Which option best explains Parse tree?

  1. Aa tree representation showing how a string is derived from a grammar
  2. Ban expression such as a(a+b)* over the alphabet {a,b}
  3. Cany set of strings formed from the symbols of that alphabet
  4. Da finite automaton equipped with a stack for recognizing context-free languages
Show Answer
Correct Answer: A. a tree representation showing how a string is derived from a grammar

Parse tree refers to a tree representation showing how a string is derived from a grammar.

Q150 Grammars & Derivations

A correct statement about Parse tree is:

  1. APDA acceptance that occurs when input is consumed and the machine is in an accepting state
  2. Ba tree representation showing how a string is derived from a grammar
  3. Cthe property that a problem has an algorithm that always halts with a yes or no answer
  4. Da finite-state machine whose output depends only on the current state
Show Answer
Correct Answer: B. a tree representation showing how a string is derived from a grammar

Parse tree refers to a tree representation showing how a string is derived from a grammar.

Q151 Grammars & Derivations

What is meant by Ambiguity in grammar in Theory of Automata?

  1. Aa language for which some Turing machine halts on every input and decides membership
  2. Ba problem whose answer is either yes or no
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. Dthe property of a grammar that allows a string to have more than one parse tree or derivation
Show Answer
Correct Answer: D. the property of a grammar that allows a string to have more than one parse tree or derivation

Ambiguity in grammar refers to the property of a grammar that allows a string to have more than one parse tree or derivation.

Q152 Grammars & Derivations

Which option best explains Ambiguity in grammar?

  1. Aa snapshot showing current state, unread input and stack contents
  2. Ba method that builds a combined automaton using ordered pairs of states
  3. Cthe property of a grammar that allows a string to have more than one parse tree or derivation
  4. Da PDA that guesses the middle of the string and matches the second half using the stack
Show Answer
Correct Answer: C. the property of a grammar that allows a string to have more than one parse tree or derivation

Ambiguity in grammar refers to the property of a grammar that allows a string to have more than one parse tree or derivation.

Q153 Grammars & Derivations

A correct statement about Ambiguity in grammar is:

  1. Aan unbounded memory divided into cells that can hold symbols
  2. Ba property decided by checking whether an accepting state is reachable through a cycle
  3. Cthe property of a grammar that allows a string to have more than one parse tree or derivation
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: C. the property of a grammar that allows a string to have more than one parse tree or derivation

Ambiguity in grammar refers to the property of a grammar that allows a string to have more than one parse tree or derivation.

Q154 Grammars & Derivations

What is meant by Unambiguous grammar in Theory of Automata?

  1. Aany set of strings formed from the symbols of that alphabet
  2. Bthe string obtained by writing the original symbols in the opposite order
  3. Ca grammar in which every generated string has only one parse tree
  4. Dan expression such as (a+b)*ab(a+b)* over {a,b}
Show Answer
Correct Answer: C. a grammar in which every generated string has only one parse tree

Unambiguous grammar refers to a grammar in which every generated string has only one parse tree.

Q155 Grammars & Derivations

Which option best explains Unambiguous grammar?

  1. Aa grammar in which at most one nonterminal appears at the left end of a production
  2. Ban operation that means either expression may be chosen
  3. Ca grammar in which every generated string has only one parse tree
  4. Da finite-state machine whose output depends on the current state and input symbol
Show Answer
Correct Answer: C. a grammar in which every generated string has only one parse tree

Unambiguous grammar refers to a grammar in which every generated string has only one parse tree.

Q156 Grammars & Derivations

A correct statement about Unambiguous grammar is:

  1. Aa property decided by checking whether an accepting state is reachable through a cycle
  2. Ba finite automaton that may have zero, one, or multiple possible moves for an input
  3. Ca necessary property used to prove that some languages are not regular
  4. Da grammar in which every generated string has only one parse tree
Show Answer
Correct Answer: D. a grammar in which every generated string has only one parse tree

Unambiguous grammar refers to a grammar in which every generated string has only one parse tree.

Q157 Grammars & Derivations

What is meant by Context-free language in Theory of Automata?

  1. APDA acceptance that occurs when input is consumed and the machine is in an accepting state
  2. Bthe string with length zero, usually denoted by ε or lambda
  3. Ca language generated by some context-free grammar
  4. Da grammar in which at most one nonterminal appears at the right end of a production
Show Answer
Correct Answer: C. a language generated by some context-free grammar

Context-free language refers to a language generated by some context-free grammar.

Q158 Grammars & Derivations

Which option best explains Context-free language?

  1. Aa language generated by some context-free grammar
  2. Ba language that contains endlessly many strings
  3. Ca graph representation of states and labeled transitions
  4. Dan alphabet whose symbols are clearly defined and can be used to build strings
Show Answer
Correct Answer: A. a language generated by some context-free grammar

Context-free language refers to a language generated by some context-free grammar.

Q159 Grammars & Derivations

A correct statement about Context-free language is:

  1. Aan operation that removes the top symbol from the stack
  2. Ba grammar symbol that cannot help derive any terminal string from the start variable
  3. Ca language generated by some context-free grammar
  4. Dthe string with length zero, usually denoted by ε or lambda
Show Answer
Correct Answer: C. a language generated by some context-free grammar

Context-free language refers to a language generated by some context-free grammar.

Q160 Grammars & Derivations

What is meant by Polish notation in Theory of Automata?

  1. Aa move that changes state without consuming an input symbol
  2. Ba finite automaton with exactly one next state for each state and input symbol
  3. Cthe action of consuming an input symbol while making a transition
  4. Da prefix notation in which the operator is written before its operands
Show Answer
Correct Answer: D. a prefix notation in which the operator is written before its operands

Polish notation refers to a prefix notation in which the operator is written before its operands.

Q161 Grammars & Derivations

Which option best explains Polish notation?

  1. Aa language that contains endlessly many strings
  2. Ba rewriting rule that replaces one symbol or pattern with another string
  3. Ca finite-state machine whose output depends only on the current state
  4. Da prefix notation in which the operator is written before its operands
Show Answer
Correct Answer: D. a prefix notation in which the operator is written before its operands

Polish notation refers to a prefix notation in which the operator is written before its operands.

Q162 Grammars & Derivations

A correct statement about Polish notation is:

  1. Aa state where the Turing machine stops computation
  2. Ba prefix notation in which the operator is written before its operands
  3. Ca definition that gives base strings and rules for generating more strings
  4. Dan expression such as a(a+b)* over the alphabet {a,b}
Show Answer
Correct Answer: B. a prefix notation in which the operator is written before its operands

Polish notation refers to a prefix notation in which the operator is written before its operands.

Q163 Grammars & Derivations

What is meant by Reverse Polish notation in Theory of Automata?

  1. Aa grammar in which every generated string has only one parse tree
  2. Ba postfix notation in which the operator is written after its operands
  3. Ca rule that writes a symbol, moves the head and changes state
  4. Dthe method of converting an NFA into an equivalent DFA using sets of NFA states
Show Answer
Correct Answer: B. a postfix notation in which the operator is written after its operands

Reverse Polish notation refers to a postfix notation in which the operator is written after its operands.

Q164 Grammars & Derivations

Which option best explains Reverse Polish notation?

  1. Aa grammar whose productions have a single nonterminal on the left side
  2. Ba postfix notation in which the operator is written after its operands
  3. Cthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  4. Da formal system of variables, terminals, productions and a start symbol
Show Answer
Correct Answer: B. a postfix notation in which the operator is written after its operands

Reverse Polish notation refers to a postfix notation in which the operator is written after its operands.

Q165 Grammars & Derivations

A correct statement about Reverse Polish notation is:

  1. Aa property decided by checking whether an accepting state is reachable through a cycle
  2. Ba finite-state machine whose output depends on the current state and input symbol
  3. Ca rule that writes a symbol, moves the head and changes state
  4. Da postfix notation in which the operator is written after its operands
Show Answer
Correct Answer: D. a postfix notation in which the operator is written after its operands

Reverse Polish notation refers to a postfix notation in which the operator is written after its operands.

Q166 Grammars & Derivations

What is meant by Regular grammar in Theory of Automata?

  1. Aa characterization of regular languages using finitely many equivalence classes of distinguishable strings
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca PDA that pushes symbols for a's and pops them while reading b's
  4. Da grammar with productions restricted to right-linear or left-linear form
Show Answer
Correct Answer: D. a grammar with productions restricted to right-linear or left-linear form

Regular grammar refers to a grammar with productions restricted to right-linear or left-linear form.

Q167 Grammars & Derivations

Which option best explains Regular grammar?

  1. Athe number of symbols occurring in a string
  2. Ba grammar symbol that cannot help derive any terminal string from the start variable
  3. Ca grammar with productions restricted to right-linear or left-linear form
  4. Da state that causes a string to be accepted when input processing ends there
Show Answer
Correct Answer: C. a grammar with productions restricted to right-linear or left-linear form

Regular grammar refers to a grammar with productions restricted to right-linear or left-linear form.

Q168 Grammars & Derivations

A correct statement about Regular grammar is:

  1. Aa grammar in which at most one nonterminal appears at the left end of a production
  2. Ba problem whose answer is either yes or no
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. Da grammar with productions restricted to right-linear or left-linear form
Show Answer
Correct Answer: D. a grammar with productions restricted to right-linear or left-linear form

Regular grammar refers to a grammar with productions restricted to right-linear or left-linear form.

Q169 Grammars & Derivations

What is meant by Right-linear grammar in Theory of Automata?

  1. Aa non-accepting state that the machine cannot escape once entered
  2. Ba PDA that guesses the middle of the string and matches the second half using the stack
  3. Ca grammar in which at most one nonterminal appears at the right end of a production
  4. DPDA acceptance that occurs when input is consumed and the stack is emptied
Show Answer
Correct Answer: C. a grammar in which at most one nonterminal appears at the right end of a production

Right-linear grammar refers to a grammar in which at most one nonterminal appears at the right end of a production.

Q170 Grammars & Derivations

Which option best explains Right-linear grammar?

  1. Aa language that contains endlessly many strings
  2. Ba grammar in which at most one nonterminal appears at the right end of a production
  3. Ca finite automaton equipped with a stack for recognizing context-free languages
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: B. a grammar in which at most one nonterminal appears at the right end of a production

Right-linear grammar refers to a grammar in which at most one nonterminal appears at the right end of a production.

Q171 Grammars & Derivations

A correct statement about Right-linear grammar is:

  1. Aan operation that means either expression may be chosen
  2. Ban unbounded memory divided into cells that can hold symbols
  3. Can expression such as (0+1)*01 over the alphabet {0,1}
  4. Da grammar in which at most one nonterminal appears at the right end of a production
Show Answer
Correct Answer: D. a grammar in which at most one nonterminal appears at the right end of a production

Right-linear grammar refers to a grammar in which at most one nonterminal appears at the right end of a production.

Q172 Grammars & Derivations

What is meant by Left-linear grammar in Theory of Automata?

  1. Aa constant length beyond which strings in an infinite regular language can be decomposed and pumped
  2. Ba finite automaton that may have zero, one, or multiple possible moves for an input
  3. Ca language for which some Turing machine halts on every input and decides membership
  4. Da grammar in which at most one nonterminal appears at the left end of a production
Show Answer
Correct Answer: D. a grammar in which at most one nonterminal appears at the left end of a production

Left-linear grammar refers to a grammar in which at most one nonterminal appears at the left end of a production.

Q173 Grammars & Derivations

Which option best explains Left-linear grammar?

  1. Aa finite automaton equipped with a stack for recognizing context-free languages
  2. Ba DFA that toggles between two states whenever symbol a is read
  3. Ca grammar in which at most one nonterminal appears at the left end of a production
  4. Da method that creates automaton states from grammar variables and transitions from productions
Show Answer
Correct Answer: C. a grammar in which at most one nonterminal appears at the left end of a production

Left-linear grammar refers to a grammar in which at most one nonterminal appears at the left end of a production.

Q174 Grammars & Derivations

A correct statement about Left-linear grammar is:

  1. Aa variable that can derive the empty string
  2. Ba grammar in which at most one nonterminal appears at the left end of a production
  3. CPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  4. Da constant length beyond which strings in an infinite regular language can be decomposed and pumped
Show Answer
Correct Answer: B. a grammar in which at most one nonterminal appears at the left end of a production

Left-linear grammar refers to a grammar in which at most one nonterminal appears at the left end of a production.

Q175 Grammars & Derivations

What is meant by FA to regular grammar conversion in Theory of Automata?

  1. Aa method that creates productions from automaton transitions and final states
  2. Ba prefix notation in which the operator is written before its operands
  3. Ca process that removes null, unit and useless productions and converts long rules into binary form
  4. Da variable symbol that can be replaced using productions
Show Answer
Correct Answer: A. a method that creates productions from automaton transitions and final states

FA to regular grammar conversion refers to a method that creates productions from automaton transitions and final states.

Q176 Grammars & Derivations

Which option best explains FA to regular grammar conversion?

  1. Aa snapshot showing current state, unread input and stack contents
  2. Bthe theorem stating that regular expressions and finite automata define the same class of languages
  3. Cthe problem of deciding whether two finite automata accept exactly the same language
  4. Da method that creates productions from automaton transitions and final states
Show Answer
Correct Answer: D. a method that creates productions from automaton transitions and final states

FA to regular grammar conversion refers to a method that creates productions from automaton transitions and final states.

Q177 Grammars & Derivations

A correct statement about FA to regular grammar conversion is:

  1. Athe classic nonregular language containing equal numbers of a's followed by b's
  2. Ba conversion that labels each incoming transition with the output of its destination state
  3. Ca method that creates productions from automaton transitions and final states
  4. Da rewriting rule that replaces one symbol or pattern with another string
Show Answer
Correct Answer: C. a method that creates productions from automaton transitions and final states

FA to regular grammar conversion refers to a method that creates productions from automaton transitions and final states.

Q178 Grammars & Derivations

What is meant by Regular grammar to FA conversion in Theory of Automata?

  1. Aa method that creates productions from automaton transitions and final states
  2. Ba method that creates automaton states from grammar variables and transitions from productions
  3. Ca named condition or memory position of the machine
  4. Da grammar whose productions have a single nonterminal on the left side
Show Answer
Correct Answer: B. a method that creates automaton states from grammar variables and transitions from productions

Regular grammar to FA conversion refers to a method that creates automaton states from grammar variables and transitions from productions.

Q179 Grammars & Derivations

Which option best explains Regular grammar to FA conversion?

  1. Aa graph representation of states and labeled transitions
  2. Ba language generated by some context-free grammar
  3. Ca method that creates automaton states from grammar variables and transitions from productions
  4. Dthe string with length zero, usually denoted by ε or lambda
Show Answer
Correct Answer: C. a method that creates automaton states from grammar variables and transitions from productions

Regular grammar to FA conversion refers to a method that creates automaton states from grammar variables and transitions from productions.

Q180 Grammars & Derivations

A correct statement about Regular grammar to FA conversion is:

  1. Aa tree representation showing how a string is derived from a grammar
  2. Ba language for which some Turing machine halts on every input and decides membership
  3. Ca method that creates automaton states from grammar variables and transitions from productions
  4. Da derivation that always replaces the rightmost nonterminal first
Show Answer
Correct Answer: C. a method that creates automaton states from grammar variables and transitions from productions

Regular grammar to FA conversion refers to a method that creates automaton states from grammar variables and transitions from productions.

Q181 Machines with Output

What is meant by Mealy machine in Theory of Automata?

  1. Aa finite-state machine whose output depends on the current state and input symbol
  2. Ba necessary property used to prove that some languages are not regular
  3. Can operation that places strings from one language directly after strings from another
  4. Da snapshot showing current state, unread input and stack contents
Show Answer
Correct Answer: A. a finite-state machine whose output depends on the current state and input symbol

Mealy machine refers to a finite-state machine whose output depends on the current state and input symbol.

Q182 Machines with Output

Which option best explains Mealy machine?

  1. Atwo strings that can be separated by some continuation leading to different acceptance results
  2. Ba finite-state machine whose output depends on the current state and input symbol
  3. Ca method that creates productions from automaton transitions and final states
  4. Da language containing no strings at all
Show Answer
Correct Answer: B. a finite-state machine whose output depends on the current state and input symbol

Mealy machine refers to a finite-state machine whose output depends on the current state and input symbol.

Q183 Machines with Output

A correct statement about Mealy machine is:

  1. Aa finite-state machine whose output depends on the current state and input symbol
  2. Ban expression such as (0+1)*01 over the alphabet {0,1}
  3. Cthe part of a Turing machine that reads, writes and moves on the tape
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: A. a finite-state machine whose output depends on the current state and input symbol

Mealy machine refers to a finite-state machine whose output depends on the current state and input symbol.

Q184 Machines with Output

What is meant by Moore machine in Theory of Automata?

  1. Aa PDA that pushes symbols for a's and pops them while reading b's
  2. Ba variable symbol that can be replaced using productions
  3. Cthe property that a problem has an algorithm that always halts with a yes or no answer
  4. Da finite-state machine whose output depends only on the current state
Show Answer
Correct Answer: D. a finite-state machine whose output depends only on the current state

Moore machine refers to a finite-state machine whose output depends only on the current state.

Q185 Machines with Output

Which option best explains Moore machine?

  1. Aa symbol that appears in final strings of the language
  2. Bthe classic nonregular language containing equal numbers of a's followed by b's
  3. Ca full snapshot of tape contents, head position and current state
  4. Da finite-state machine whose output depends only on the current state
Show Answer
Correct Answer: D. a finite-state machine whose output depends only on the current state

Moore machine refers to a finite-state machine whose output depends only on the current state.

Q186 Machines with Output

A correct statement about Moore machine is:

  1. Aa PDA that pushes symbols for a's and pops them while reading b's
  2. Ba finite sequence of symbols chosen from an alphabet
  3. Ca finite-state machine whose output depends only on the current state
  4. Da property decided by checking whether an accepting state is reachable through a cycle
Show Answer
Correct Answer: C. a finite-state machine whose output depends only on the current state

Moore machine refers to a finite-state machine whose output depends only on the current state.

Q187 Machines with Output

What is meant by Moore to Mealy conversion in Theory of Automata?

  1. Aa variable that can derive the empty string
  2. Ba language that contains endlessly many strings
  3. Ca graph representation of states and labeled transitions
  4. Da conversion that labels each incoming transition with the output of its destination state
Show Answer
Correct Answer: D. a conversion that labels each incoming transition with the output of its destination state

Moore to Mealy conversion refers to a conversion that labels each incoming transition with the output of its destination state.

Q188 Machines with Output

Which option best explains Moore to Mealy conversion?

  1. Aan expression such as (a+b)*ab(a+b)* over {a,b}
  2. Ba conversion that labels each incoming transition with the output of its destination state
  3. Ca grammar in which at most one nonterminal appears at the right end of a production
  4. Dthe property that a problem has an algorithm that always halts with a yes or no answer
Show Answer
Correct Answer: B. a conversion that labels each incoming transition with the output of its destination state

Moore to Mealy conversion refers to a conversion that labels each incoming transition with the output of its destination state.

Q189 Machines with Output

A correct statement about Moore to Mealy conversion is:

  1. Aa grammar whose productions have a single nonterminal on the left side
  2. Ba conversion that labels each incoming transition with the output of its destination state
  3. Cthe string obtained by writing the original symbols in the opposite order
  4. Da language that can be recognized by a finite automaton
Show Answer
Correct Answer: B. a conversion that labels each incoming transition with the output of its destination state

Moore to Mealy conversion refers to a conversion that labels each incoming transition with the output of its destination state.

Q190 Machines with Output

What is meant by Mealy to Moore conversion in Theory of Automata?

  1. Aa DFA that toggles between two states whenever symbol a is read
  2. Bthe expression (0+1)*, which represents every string over {0,1}
  3. Ctwo strings that can be separated by some continuation leading to different acceptance results
  4. Da conversion that may split states so outputs become associated with states
Show Answer
Correct Answer: D. a conversion that may split states so outputs become associated with states

Mealy to Moore conversion refers to a conversion that may split states so outputs become associated with states.

Q191 Machines with Output

Which option best explains Mealy to Moore conversion?

  1. Aa mathematical machine with finitely many states used to recognize regular languages
  2. Ban expression such as (a+b)*ab(a+b)* over {a,b}
  3. Ca language that contains only a limited number of strings
  4. Da conversion that may split states so outputs become associated with states
Show Answer
Correct Answer: D. a conversion that may split states so outputs become associated with states

Mealy to Moore conversion refers to a conversion that may split states so outputs become associated with states.

Q192 Machines with Output

A correct statement about Mealy to Moore conversion is:

  1. Aa language that cannot be recognized by any finite automaton
  2. Bthe expression (0+1)*, which represents every string over {0,1}
  3. Ca conversion that may split states so outputs become associated with states
  4. Dthe action of consuming an input symbol while making a transition
Show Answer
Correct Answer: C. a conversion that may split states so outputs become associated with states

Mealy to Moore conversion refers to a conversion that may split states so outputs become associated with states.

Q193 Non-Regular Languages

What is meant by Nonregular language in Theory of Automata?

  1. Aa language that cannot be recognized by any finite automaton
  2. Ba state where the Turing machine stops computation
  3. Cthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
  4. Da method that creates productions from automaton transitions and final states
Show Answer
Correct Answer: A. a language that cannot be recognized by any finite automaton

Nonregular language refers to a language that cannot be recognized by any finite automaton.

Q194 Non-Regular Languages

Which option best explains Nonregular language?

  1. Aa language that cannot be recognized by any finite automaton
  2. Ban expression such as a(a+b)* over the alphabet {a,b}
  3. Ca property decided by checking whether an accepting state is reachable through a cycle
  4. Da full snapshot of tape contents, head position and current state
Show Answer
Correct Answer: A. a language that cannot be recognized by any finite automaton

Nonregular language refers to a language that cannot be recognized by any finite automaton.

Q195 Non-Regular Languages

A correct statement about Nonregular language is:

  1. Aa snapshot showing current state, unread input and stack contents
  2. Bthe theorem stating that regular expressions and finite automata define the same class of languages
  3. Can abstract computational model with a tape, head, states and transition rules
  4. Da language that cannot be recognized by any finite automaton
Show Answer
Correct Answer: D. a language that cannot be recognized by any finite automaton

Nonregular language refers to a language that cannot be recognized by any finite automaton.

Q196 Non-Regular Languages

What is meant by Pumping lemma for regular languages in Theory of Automata?

  1. Athe state from which computation begins
  2. Ba method that creates productions from automaton transitions and final states
  3. Cthe theorem stating that regular expressions and finite automata define the same class of languages
  4. Da necessary property used to prove that some languages are not regular
Show Answer
Correct Answer: D. a necessary property used to prove that some languages are not regular

Pumping lemma for regular languages refers to a necessary property used to prove that some languages are not regular.

Q197 Non-Regular Languages

Which option best explains Pumping lemma for regular languages?

  1. Aa non-accepting state that the machine cannot escape once entered
  2. Ba derivation that always replaces the rightmost nonterminal first
  3. Ca necessary property used to prove that some languages are not regular
  4. Dan operation that removes the top symbol from the stack
Show Answer
Correct Answer: C. a necessary property used to prove that some languages are not regular

Pumping lemma for regular languages refers to a necessary property used to prove that some languages are not regular.

Q198 Non-Regular Languages

A correct statement about Pumping lemma for regular languages is:

  1. Aa finite non-empty set of symbols used to form strings
  2. Ba problem whose answer is either yes or no
  3. Ca language that can be recognized by a finite automaton
  4. Da necessary property used to prove that some languages are not regular
Show Answer
Correct Answer: D. a necessary property used to prove that some languages are not regular

Pumping lemma for regular languages refers to a necessary property used to prove that some languages are not regular.

Q199 Non-Regular Languages

What is meant by Pumping length in Theory of Automata?

  1. Aa constant length beyond which strings in an infinite regular language can be decomposed and pumped
  2. Ba Turing machine strategy that repeatedly marks matching a's and b's
  3. Ca variable that can derive the empty string
  4. Dan operation that places a symbol on the top of the stack
Show Answer
Correct Answer: A. a constant length beyond which strings in an infinite regular language can be decomposed and pumped

Pumping length refers to a constant length beyond which strings in an infinite regular language can be decomposed and pumped.

Q200 Non-Regular Languages

Which option best explains Pumping length?

  1. Aa graph representation of states and labeled transitions
  2. Ba constant length beyond which strings in an infinite regular language can be decomposed and pumped
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. DPDA acceptance that occurs when input is consumed and the stack is emptied
Show Answer
Correct Answer: B. a constant length beyond which strings in an infinite regular language can be decomposed and pumped

Pumping length refers to a constant length beyond which strings in an infinite regular language can be decomposed and pumped.

Q201 Non-Regular Languages

A correct statement about Pumping length is:

  1. Aa constant length beyond which strings in an infinite regular language can be decomposed and pumped
  2. Ba PDA that pushes symbols for a's and pops them while reading b's
  3. Ca full snapshot of tape contents, head position and current state
  4. Dthe language obtained by changing accepting states to non-accepting states and vice versa in a complete DFA
Show Answer
Correct Answer: A. a constant length beyond which strings in an infinite regular language can be decomposed and pumped

Pumping length refers to a constant length beyond which strings in an infinite regular language can be decomposed and pumped.

Q202 Non-Regular Languages

What is meant by Myhill-Nerode theorem in Theory of Automata?

  1. Aa characterization of regular languages using finitely many equivalence classes of distinguishable strings
  2. Ba PDA that guesses the middle of the string and matches the second half using the stack
  3. Can unbounded memory divided into cells that can hold symbols
  4. Dthe string with length zero, usually denoted by ε or lambda
Show Answer
Correct Answer: A. a characterization of regular languages using finitely many equivalence classes of distinguishable strings

Myhill-Nerode theorem refers to a characterization of regular languages using finitely many equivalence classes of distinguishable strings.

Q203 Non-Regular Languages

Which option best explains Myhill-Nerode theorem?

  1. Aa CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  2. Ba characterization of regular languages using finitely many equivalence classes of distinguishable strings
  3. Cthe action of consuming an input symbol while making a transition
  4. Dany string of terminals and nonterminals produced during a derivation
Show Answer
Correct Answer: B. a characterization of regular languages using finitely many equivalence classes of distinguishable strings

Myhill-Nerode theorem refers to a characterization of regular languages using finitely many equivalence classes of distinguishable strings.

Q204 Non-Regular Languages

A correct statement about Myhill-Nerode theorem is:

  1. Aa characterization of regular languages using finitely many equivalence classes of distinguishable strings
  2. Ba prefix notation in which the operator is written before its operands
  3. Ca grammar whose productions have a single nonterminal on the left side
  4. Da variable that can derive the empty string
Show Answer
Correct Answer: A. a characterization of regular languages using finitely many equivalence classes of distinguishable strings

Myhill-Nerode theorem refers to a characterization of regular languages using finitely many equivalence classes of distinguishable strings.

Q205 Non-Regular Languages

What is meant by Distinguishable strings in Theory of Automata?

  1. Atwo strings that can be separated by some continuation leading to different acceptance results
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca property decided by checking whether an accepting state is reachable through a cycle
  4. Da characterization of regular languages using finitely many equivalence classes of distinguishable strings
Show Answer
Correct Answer: A. two strings that can be separated by some continuation leading to different acceptance results

Distinguishable strings refers to two strings that can be separated by some continuation leading to different acceptance results.

Q206 Non-Regular Languages

Which option best explains Distinguishable strings?

  1. Atwo strings that can be separated by some continuation leading to different acceptance results
  2. Ba language that can be recognized by a finite automaton
  3. Ca finite-state machine whose output depends only on the current state
  4. Da variable that can derive the empty string
Show Answer
Correct Answer: A. two strings that can be separated by some continuation leading to different acceptance results

Distinguishable strings refers to two strings that can be separated by some continuation leading to different acceptance results.

Q207 Non-Regular Languages

A correct statement about Distinguishable strings is:

  1. Aany set of strings formed from the symbols of that alphabet
  2. Btwo strings that can be separated by some continuation leading to different acceptance results
  3. Ca production of the form A→B where both sides are single variables
  4. Dthe expression (0+1)*, which represents every string over {0,1}
Show Answer
Correct Answer: B. two strings that can be separated by some continuation leading to different acceptance results

Distinguishable strings refers to two strings that can be separated by some continuation leading to different acceptance results.

Q208 Non-Regular Languages

What is meant by Language a^n b^n in Theory of Automata?

  1. Aa language that contains endlessly many strings
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca last-in first-out memory structure used by a pushdown automaton
  4. Dthe classic nonregular language containing equal numbers of a's followed by b's
Show Answer
Correct Answer: D. the classic nonregular language containing equal numbers of a's followed by b's

Language a^n b^n refers to the classic nonregular language containing equal numbers of a's followed by b's.

Q209 Non-Regular Languages

Which option best explains Language a^n b^n?

  1. Atwo strings that can be separated by some continuation leading to different acceptance results
  2. Ban operation that means either expression may be chosen
  3. Cthe classic nonregular language containing equal numbers of a's followed by b's
  4. Da method that creates productions from automaton transitions and final states
Show Answer
Correct Answer: C. the classic nonregular language containing equal numbers of a's followed by b's

Language a^n b^n refers to the classic nonregular language containing equal numbers of a's followed by b's.

Q210 Non-Regular Languages

A correct statement about Language a^n b^n is:

  1. Aa derivation that always replaces the rightmost nonterminal first
  2. Bthe classic nonregular language containing equal numbers of a's followed by b's
  3. Cthe action of consuming an input symbol while making a transition
  4. Dan abstract computational model with a tape, head, states and transition rules
Show Answer
Correct Answer: B. the classic nonregular language containing equal numbers of a's followed by b's

Language a^n b^n refers to the classic nonregular language containing equal numbers of a's followed by b's.

Q211 Decision Problems

What is meant by Finiteness of regular languages in Theory of Automata?

  1. Aan alphabet whose symbols are clearly defined and can be used to build strings
  2. Ba finite-state machine whose output depends on the current state and input symbol
  3. Ca property decided by checking whether an accepting state is reachable through a cycle
  4. Da PDA that pushes symbols for a's and pops them while reading b's
Show Answer
Correct Answer: C. a property decided by checking whether an accepting state is reachable through a cycle

Finiteness of regular languages refers to a property decided by checking whether an accepting state is reachable through a cycle.

Q212 Decision Problems

Which option best explains Finiteness of regular languages?

  1. Aan unbounded memory divided into cells that can hold symbols
  2. Ba string that reads the same from left to right and right to left
  3. Can abstract computational model with a tape, head, states and transition rules
  4. Da property decided by checking whether an accepting state is reachable through a cycle
Show Answer
Correct Answer: D. a property decided by checking whether an accepting state is reachable through a cycle

Finiteness of regular languages refers to a property decided by checking whether an accepting state is reachable through a cycle.

Q213 Decision Problems

A correct statement about Finiteness of regular languages is:

  1. Aa property decided by checking whether an accepting state is reachable through a cycle
  2. Ba symbolic notation used to describe regular languages
  3. Cthe part of a Turing machine that reads, writes and moves on the tape
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: A. a property decided by checking whether an accepting state is reachable through a cycle

Finiteness of regular languages refers to a property decided by checking whether an accepting state is reachable through a cycle.

Q214 Pushdown Automata

What is meant by Pushdown automaton in Theory of Automata?

  1. Aa conversion that may split states so outputs become associated with states
  2. Ba symbolic notation used to describe regular languages
  3. Ca finite automaton equipped with a stack for recognizing context-free languages
  4. Dthe theorem stating that regular expressions and finite automata define the same class of languages
Show Answer
Correct Answer: C. a finite automaton equipped with a stack for recognizing context-free languages

Pushdown automaton refers to a finite automaton equipped with a stack for recognizing context-free languages.

Q215 Pushdown Automata

Which option best explains Pushdown automaton?

  1. Aa method that creates productions from automaton transitions and final states
  2. Ba tree representation showing how a string is derived from a grammar
  3. Ca derivation that always replaces the leftmost nonterminal first
  4. Da finite automaton equipped with a stack for recognizing context-free languages
Show Answer
Correct Answer: D. a finite automaton equipped with a stack for recognizing context-free languages

Pushdown automaton refers to a finite automaton equipped with a stack for recognizing context-free languages.

Q216 Pushdown Automata

A correct statement about Pushdown automaton is:

  1. Aa prefix notation in which the operator is written before its operands
  2. Bthe part of a Turing machine that reads, writes and moves on the tape
  3. Ca language containing no strings at all
  4. Da finite automaton equipped with a stack for recognizing context-free languages
Show Answer
Correct Answer: D. a finite automaton equipped with a stack for recognizing context-free languages

Pushdown automaton refers to a finite automaton equipped with a stack for recognizing context-free languages.

Q217 Pushdown Automata

What is meant by Stack in PDA in Theory of Automata?

  1. Aa last-in first-out memory structure used by a pushdown automaton
  2. Ba finite sequence of symbols chosen from an alphabet
  3. Ca move that changes state without consuming an input symbol
  4. Dthe property that a problem has an algorithm that always halts with a yes or no answer
Show Answer
Correct Answer: A. a last-in first-out memory structure used by a pushdown automaton

Stack in PDA refers to a last-in first-out memory structure used by a pushdown automaton.

Q218 Pushdown Automata

Which option best explains Stack in PDA?

  1. Aa last-in first-out memory structure used by a pushdown automaton
  2. Ba non-accepting state that the machine cannot escape once entered
  3. Cany string of terminals and nonterminals produced during a derivation
  4. Da grammar in which at most one nonterminal appears at the right end of a production
Show Answer
Correct Answer: A. a last-in first-out memory structure used by a pushdown automaton

Stack in PDA refers to a last-in first-out memory structure used by a pushdown automaton.

Q219 Pushdown Automata

A correct statement about Stack in PDA is:

  1. Aa last-in first-out memory structure used by a pushdown automaton
  2. Bthe distinguished nonterminal from which derivation begins
  3. Can unbounded memory divided into cells that can hold symbols
  4. Dthe classic nonregular language containing equal numbers of a's followed by b's
Show Answer
Correct Answer: A. a last-in first-out memory structure used by a pushdown automaton

Stack in PDA refers to a last-in first-out memory structure used by a pushdown automaton.

Q220 Pushdown Automata

What is meant by Push operation in Theory of Automata?

  1. Aan operation that means either expression may be chosen
  2. Ban operation that places a symbol on the top of the stack
  3. Ca method that creates productions from automaton transitions and final states
  4. Da named condition or memory position of the machine
Show Answer
Correct Answer: B. an operation that places a symbol on the top of the stack

Push operation refers to an operation that places a symbol on the top of the stack.

Q221 Pushdown Automata

Which option best explains Push operation?

  1. APDA acceptance that occurs when input is consumed and the machine is in an accepting state
  2. Ban abstract computational model with a tape, head, states and transition rules
  3. Can operation that places a symbol on the top of the stack
  4. Dan unbounded memory divided into cells that can hold symbols
Show Answer
Correct Answer: C. an operation that places a symbol on the top of the stack

Push operation refers to an operation that places a symbol on the top of the stack.

Q222 Pushdown Automata

A correct statement about Push operation is:

  1. Aan operation that places a symbol on the top of the stack
  2. Ba last-in first-out memory structure used by a pushdown automaton
  3. Ca DFA that toggles between two states whenever symbol a is read
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: A. an operation that places a symbol on the top of the stack

Push operation refers to an operation that places a symbol on the top of the stack.

Q223 Pushdown Automata

What is meant by Pop operation in Theory of Automata?

  1. Athe rule that tells the automaton which state to move to after reading a symbol
  2. Ban operation that removes the top symbol from the stack
  3. Ca snapshot showing current state, unread input and stack contents
  4. Da graph representation of states and labeled transitions
Show Answer
Correct Answer: B. an operation that removes the top symbol from the stack

Pop operation refers to an operation that removes the top symbol from the stack.

Q224 Pushdown Automata

Which option best explains Pop operation?

  1. Athe expression (0+1)*, which represents every string over {0,1}
  2. Ban operation that removes the top symbol from the stack
  3. Ca move that changes state without consuming an input symbol
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: B. an operation that removes the top symbol from the stack

Pop operation refers to an operation that removes the top symbol from the stack.

Q225 Pushdown Automata

A correct statement about Pop operation is:

  1. Aan operation that places strings from one language directly after strings from another
  2. Ban operation that removes the top symbol from the stack
  3. Can alphabet whose symbols are clearly defined and can be used to build strings
  4. Da rule that writes a symbol, moves the head and changes state
Show Answer
Correct Answer: B. an operation that removes the top symbol from the stack

Pop operation refers to an operation that removes the top symbol from the stack.

Q226 Pushdown Automata

What is meant by Read operation in PDA in Theory of Automata?

  1. Aa finite non-empty set of symbols used to form strings
  2. Ba snapshot showing current state, unread input and stack contents
  3. Cthe action of consuming an input symbol while making a transition
  4. Da grammar whose productions have a single nonterminal on the left side
Show Answer
Correct Answer: C. the action of consuming an input symbol while making a transition

Read operation in PDA refers to the action of consuming an input symbol while making a transition.

Q227 Pushdown Automata

Which option best explains Read operation in PDA?

  1. Aa production that derives the empty string
  2. Bthe action of consuming an input symbol while making a transition
  3. Ca prefix notation in which the operator is written before its operands
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: B. the action of consuming an input symbol while making a transition

Read operation in PDA refers to the action of consuming an input symbol while making a transition.

Q228 Pushdown Automata

A correct statement about Read operation in PDA is:

  1. Aany string of terminals and nonterminals produced during a derivation
  2. Bthe action of consuming an input symbol while making a transition
  3. Ca grammar in which at most one nonterminal appears at the left end of a production
  4. Da finite-state machine whose output depends on the current state and input symbol
Show Answer
Correct Answer: B. the action of consuming an input symbol while making a transition

Read operation in PDA refers to the action of consuming an input symbol while making a transition.

Q229 Pushdown Automata

What is meant by PDA instantaneous description in Theory of Automata?

  1. Aa snapshot showing current state, unread input and stack contents
  2. Bthe ability of a PDA to choose among multiple valid transitions
  3. Cthe string with length zero, usually denoted by ε or lambda
  4. Da CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
Show Answer
Correct Answer: A. a snapshot showing current state, unread input and stack contents

PDA instantaneous description refers to a snapshot showing current state, unread input and stack contents.

Q230 Pushdown Automata

Which option best explains PDA instantaneous description?

  1. Aa finite-state machine whose output depends only on the current state
  2. Bthe string obtained by writing the original symbols in the opposite order
  3. Ca grammar in which every generated string has only one parse tree
  4. Da snapshot showing current state, unread input and stack contents
Show Answer
Correct Answer: D. a snapshot showing current state, unread input and stack contents

PDA instantaneous description refers to a snapshot showing current state, unread input and stack contents.

Q231 Pushdown Automata

A correct statement about PDA instantaneous description is:

  1. Aa grammar in which at most one nonterminal appears at the right end of a production
  2. Bthe problem of deciding whether a finite automaton accepts at least one string
  3. Ca snapshot showing current state, unread input and stack contents
  4. Da conversion that labels each incoming transition with the output of its destination state
Show Answer
Correct Answer: C. a snapshot showing current state, unread input and stack contents

PDA instantaneous description refers to a snapshot showing current state, unread input and stack contents.

Q232 Pushdown Automata

What is meant by Acceptance by final state in Theory of Automata?

  1. APDA acceptance that occurs when input is consumed and the stack is emptied
  2. Ba string that reads the same from left to right and right to left
  3. CPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  4. Dthe expression (0+1)*, which represents every string over {0,1}
Show Answer
Correct Answer: C. PDA acceptance that occurs when input is consumed and the machine is in an accepting state

Acceptance by final state refers to PDA acceptance that occurs when input is consumed and the machine is in an accepting state.

Q233 Pushdown Automata

Which option best explains Acceptance by final state?

  1. Aa derivation that always replaces the rightmost nonterminal first
  2. BPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  3. Ca snapshot showing current state, unread input and stack contents
  4. Da characterization of regular languages using finitely many equivalence classes of distinguishable strings
Show Answer
Correct Answer: B. PDA acceptance that occurs when input is consumed and the machine is in an accepting state

Acceptance by final state refers to PDA acceptance that occurs when input is consumed and the machine is in an accepting state.

Q234 Pushdown Automata

A correct statement about Acceptance by final state is:

  1. Aa language containing no strings at all
  2. Ba symbolic notation used to describe regular languages
  3. CPDA acceptance that occurs when input is consumed and the machine is in an accepting state
  4. Da problem whose answer is either yes or no
Show Answer
Correct Answer: C. PDA acceptance that occurs when input is consumed and the machine is in an accepting state

Acceptance by final state refers to PDA acceptance that occurs when input is consumed and the machine is in an accepting state.

Q235 Pushdown Automata

What is meant by Acceptance by empty stack in Theory of Automata?

  1. Aa graph representation of states and labeled transitions
  2. Ba variable symbol that can be replaced using productions
  3. Ca language generated by some context-free grammar
  4. DPDA acceptance that occurs when input is consumed and the stack is emptied
Show Answer
Correct Answer: D. PDA acceptance that occurs when input is consumed and the stack is emptied

Acceptance by empty stack refers to PDA acceptance that occurs when input is consumed and the stack is emptied.

Q236 Pushdown Automata

Which option best explains Acceptance by empty stack?

  1. Aa CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  2. Ba formal system of variables, terminals, productions and a start symbol
  3. Ca language containing no strings at all
  4. DPDA acceptance that occurs when input is consumed and the stack is emptied
Show Answer
Correct Answer: D. PDA acceptance that occurs when input is consumed and the stack is emptied

Acceptance by empty stack refers to PDA acceptance that occurs when input is consumed and the stack is emptied.

Q237 Pushdown Automata

A correct statement about Acceptance by empty stack is:

  1. Aan expression such as (0+1)*01 over the alphabet {0,1}
  2. Ba Turing machine strategy that repeatedly marks matching a's and b's
  3. Ca derivation that always replaces the leftmost nonterminal first
  4. DPDA acceptance that occurs when input is consumed and the stack is emptied
Show Answer
Correct Answer: D. PDA acceptance that occurs when input is consumed and the stack is emptied

Acceptance by empty stack refers to PDA acceptance that occurs when input is consumed and the stack is emptied.

Q238 Pushdown Automata

What is meant by Nondeterminism in PDA in Theory of Automata?

  1. Athe ability of a PDA to choose among multiple valid transitions
  2. Ba language that contains endlessly many strings
  3. Ca grammar with productions restricted to right-linear or left-linear form
  4. Da language that contains only a limited number of strings
Show Answer
Correct Answer: A. the ability of a PDA to choose among multiple valid transitions

Nondeterminism in PDA refers to the ability of a PDA to choose among multiple valid transitions.

Q239 Pushdown Automata

Which option best explains Nondeterminism in PDA?

  1. Aa finite automaton equipped with a stack for recognizing context-free languages
  2. Ban operation that places strings from one language directly after strings from another
  3. Cthe ability of a PDA to choose among multiple valid transitions
  4. Dthe string obtained by writing the original symbols in the opposite order
Show Answer
Correct Answer: C. the ability of a PDA to choose among multiple valid transitions

Nondeterminism in PDA refers to the ability of a PDA to choose among multiple valid transitions.

Q240 Pushdown Automata

A correct statement about Nondeterminism in PDA is:

  1. Athe distinguished nonterminal from which derivation begins
  2. Ba language generated by some context-free grammar
  3. Ca state where the Turing machine stops computation
  4. Dthe ability of a PDA to choose among multiple valid transitions
Show Answer
Correct Answer: D. the ability of a PDA to choose among multiple valid transitions

Nondeterminism in PDA refers to the ability of a PDA to choose among multiple valid transitions.

Q241 Pushdown Automata

What is meant by PDA for a^n b^n in Theory of Automata?

  1. Aa snapshot showing current state, unread input and stack contents
  2. Ba PDA that pushes symbols for a's and pops them while reading b's
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. Da directed labeled graph used to represent language recognition paths
Show Answer
Correct Answer: B. a PDA that pushes symbols for a's and pops them while reading b's

PDA for a^n b^n refers to a PDA that pushes symbols for a's and pops them while reading b's.

Q242 Pushdown Automata

Which option best explains PDA for a^n b^n?

  1. Aa finite-state machine whose output depends only on the current state
  2. Ba PDA that pushes symbols for a's and pops them while reading b's
  3. Can expression such as (0+1)*01 over the alphabet {0,1}
  4. Da rule that writes a symbol, moves the head and changes state
Show Answer
Correct Answer: B. a PDA that pushes symbols for a's and pops them while reading b's

PDA for a^n b^n refers to a PDA that pushes symbols for a's and pops them while reading b's.

Q243 Pushdown Automata

A correct statement about PDA for a^n b^n is:

  1. Aa derivation that always replaces the leftmost nonterminal first
  2. Ba finite automaton equipped with a stack for recognizing context-free languages
  3. Ca PDA that pushes symbols for a's and pops them while reading b's
  4. Da symbolic notation used to describe regular languages
Show Answer
Correct Answer: C. a PDA that pushes symbols for a's and pops them while reading b's

PDA for a^n b^n refers to a PDA that pushes symbols for a's and pops them while reading b's.

Q244 Pushdown Automata

What is meant by PDA for palindrome in Theory of Automata?

  1. Aa PDA that guesses the middle of the string and matches the second half using the stack
  2. Ba finite automaton equipped with a stack for recognizing context-free languages
  3. Ca process that removes null, unit and useless productions and converts long rules into binary form
  4. Da postfix notation in which the operator is written after its operands
Show Answer
Correct Answer: A. a PDA that guesses the middle of the string and matches the second half using the stack

PDA for palindrome refers to a PDA that guesses the middle of the string and matches the second half using the stack.

Q245 Pushdown Automata

Which option best explains PDA for palindrome?

  1. Aan alphabet whose symbols are clearly defined and can be used to build strings
  2. Ba PDA that guesses the middle of the string and matches the second half using the stack
  3. Ca finite automaton with exactly one next state for each state and input symbol
  4. Da finite automaton that may have zero, one, or multiple possible moves for an input
Show Answer
Correct Answer: B. a PDA that guesses the middle of the string and matches the second half using the stack

PDA for palindrome refers to a PDA that guesses the middle of the string and matches the second half using the stack.

Q246 Pushdown Automata

A correct statement about PDA for palindrome is:

  1. Aa finite automaton with exactly one next state for each state and input symbol
  2. Bthe expression (0+1)*, which represents every string over {0,1}
  3. Ca mathematically defined set of strings over a specified alphabet
  4. Da PDA that guesses the middle of the string and matches the second half using the stack
Show Answer
Correct Answer: D. a PDA that guesses the middle of the string and matches the second half using the stack

PDA for palindrome refers to a PDA that guesses the middle of the string and matches the second half using the stack.

Q247 Turing Machines & Decidability

What is meant by Turing machine in Theory of Automata?

  1. Aa PDA that guesses the middle of the string and matches the second half using the stack
  2. Ban abstract computational model with a tape, head, states and transition rules
  3. Can alphabet whose symbols are clearly defined and can be used to build strings
  4. Da production that derives the empty string
Show Answer
Correct Answer: B. an abstract computational model with a tape, head, states and transition rules

Turing machine refers to an abstract computational model with a tape, head, states and transition rules.

Q248 Turing Machines & Decidability

Which option best explains Turing machine?

  1. Aan abstract computational model with a tape, head, states and transition rules
  2. Ba prefix notation in which the operator is written before its operands
  3. Ca derivation that always replaces the rightmost nonterminal first
  4. Da method that creates productions from automaton transitions and final states
Show Answer
Correct Answer: A. an abstract computational model with a tape, head, states and transition rules

Turing machine refers to an abstract computational model with a tape, head, states and transition rules.

Q249 Turing Machines & Decidability

A correct statement about Turing machine is:

  1. Athe problem of deciding whether two finite automata accept exactly the same language
  2. Ba grammar whose productions have a single nonterminal on the left side
  3. Can abstract computational model with a tape, head, states and transition rules
  4. Da directed labeled graph used to represent language recognition paths
Show Answer
Correct Answer: C. an abstract computational model with a tape, head, states and transition rules

Turing machine refers to an abstract computational model with a tape, head, states and transition rules.

Q250 Turing Machines & Decidability

What is meant by Tape of a Turing machine in Theory of Automata?

  1. Aa production of the form A→B where both sides are single variables
  2. Ban unbounded memory divided into cells that can hold symbols
  3. Cthe ability of a PDA to choose among multiple valid transitions
  4. Dan expression such as a(a+b)* over the alphabet {a,b}
Show Answer
Correct Answer: B. an unbounded memory divided into cells that can hold symbols

Tape of a Turing machine refers to an unbounded memory divided into cells that can hold symbols.

Q251 Turing Machines & Decidability

Which option best explains Tape of a Turing machine?

  1. Aa finite automaton that may have zero, one, or multiple possible moves for an input
  2. Ba rule that writes a symbol, moves the head and changes state
  3. Ca grammar in which at most one nonterminal appears at the right end of a production
  4. Dan unbounded memory divided into cells that can hold symbols
Show Answer
Correct Answer: D. an unbounded memory divided into cells that can hold symbols

Tape of a Turing machine refers to an unbounded memory divided into cells that can hold symbols.

Q252 Turing Machines & Decidability

A correct statement about Tape of a Turing machine is:

  1. Aan unbounded memory divided into cells that can hold symbols
  2. Bthe rule that tells the automaton which state to move to after reading a symbol
  3. Ca finite automaton that may have zero, one, or multiple possible moves for an input
  4. Da prefix notation in which the operator is written before its operands
Show Answer
Correct Answer: A. an unbounded memory divided into cells that can hold symbols

Tape of a Turing machine refers to an unbounded memory divided into cells that can hold symbols.

Q253 Turing Machines & Decidability

What is meant by Read-write head in Theory of Automata?

  1. Aa symbolic notation used to describe regular languages
  2. Bthe method of converting an NFA into an equivalent DFA using sets of NFA states
  3. Ca full snapshot of tape contents, head position and current state
  4. Dthe part of a Turing machine that reads, writes and moves on the tape
Show Answer
Correct Answer: D. the part of a Turing machine that reads, writes and moves on the tape

Read-write head refers to the part of a Turing machine that reads, writes and moves on the tape.

Q254 Turing Machines & Decidability

Which option best explains Read-write head?

  1. Aa tabular representation of state changes for each input symbol
  2. Bthe property of a grammar that allows a string to have more than one parse tree or derivation
  3. Cthe part of a Turing machine that reads, writes and moves on the tape
  4. Dthe string with length zero, usually denoted by ε or lambda
Show Answer
Correct Answer: C. the part of a Turing machine that reads, writes and moves on the tape

Read-write head refers to the part of a Turing machine that reads, writes and moves on the tape.

Q255 Turing Machines & Decidability

A correct statement about Read-write head is:

  1. Athe theorem stating that regular expressions and finite automata define the same class of languages
  2. Ba process that removes null, unit and useless productions and converts long rules into binary form
  3. Cthe part of a Turing machine that reads, writes and moves on the tape
  4. Dthe rule that tells the automaton which state to move to after reading a symbol
Show Answer
Correct Answer: C. the part of a Turing machine that reads, writes and moves on the tape

Read-write head refers to the part of a Turing machine that reads, writes and moves on the tape.

Q256 Turing Machines & Decidability

What is meant by Turing machine transition in Theory of Automata?

  1. Aa grammar whose productions have a single nonterminal on the left side
  2. Ban operation that means either expression may be chosen
  3. Ca mathematically defined set of strings over a specified alphabet
  4. Da rule that writes a symbol, moves the head and changes state
Show Answer
Correct Answer: D. a rule that writes a symbol, moves the head and changes state

Turing machine transition refers to a rule that writes a symbol, moves the head and changes state.

Q257 Turing Machines & Decidability

Which option best explains Turing machine transition?

  1. Aa mathematical machine with finitely many states used to recognize regular languages
  2. Ba rule that writes a symbol, moves the head and changes state
  3. Ca derivation that always replaces the rightmost nonterminal first
  4. Dan operation that places strings from one language directly after strings from another
Show Answer
Correct Answer: B. a rule that writes a symbol, moves the head and changes state

Turing machine transition refers to a rule that writes a symbol, moves the head and changes state.

Q258 Turing Machines & Decidability

A correct statement about Turing machine transition is:

  1. Aa production that derives the empty string
  2. Ba rule that writes a symbol, moves the head and changes state
  3. Cthe property of a grammar that allows a string to have more than one parse tree or derivation
  4. Dany set of strings formed from the symbols of that alphabet
Show Answer
Correct Answer: B. a rule that writes a symbol, moves the head and changes state

Turing machine transition refers to a rule that writes a symbol, moves the head and changes state.

Q259 Turing Machines & Decidability

What is meant by Halting state in Theory of Automata?

  1. Aa method that creates productions from automaton transitions and final states
  2. Bany set of strings formed from the symbols of that alphabet
  3. Ca formal system of variables, terminals, productions and a start symbol
  4. Da state where the Turing machine stops computation
Show Answer
Correct Answer: D. a state where the Turing machine stops computation

Halting state refers to a state where the Turing machine stops computation.

Q260 Turing Machines & Decidability

Which option best explains Halting state?

  1. Aa state where the Turing machine stops computation
  2. Ba PDA that guesses the middle of the string and matches the second half using the stack
  3. Ca language for which some Turing machine halts on every input and decides membership
  4. Da prefix notation in which the operator is written before its operands
Show Answer
Correct Answer: A. a state where the Turing machine stops computation

Halting state refers to a state where the Turing machine stops computation.

Q261 Turing Machines & Decidability

A correct statement about Halting state is:

  1. Aa finite non-empty set of symbols used to form strings
  2. Ba grammar whose productions have a single nonterminal on the left side
  3. Can expression such as (a+b)*ab(a+b)* over {a,b}
  4. Da state where the Turing machine stops computation
Show Answer
Correct Answer: D. a state where the Turing machine stops computation

Halting state refers to a state where the Turing machine stops computation.

Q262 Turing Machines & Decidability

What is meant by Configuration of a Turing machine in Theory of Automata?

  1. Aa language that contains endlessly many strings
  2. Ba definition that gives base strings and rules for generating more strings
  3. Ca full snapshot of tape contents, head position and current state
  4. Da grammar with productions restricted to right-linear or left-linear form
Show Answer
Correct Answer: C. a full snapshot of tape contents, head position and current state

Configuration of a Turing machine refers to a full snapshot of tape contents, head position and current state.

Q263 Turing Machines & Decidability

Which option best explains Configuration of a Turing machine?

  1. Aa characterization of regular languages using finitely many equivalence classes of distinguishable strings
  2. Ba language that contains only a limited number of strings
  3. Ca full snapshot of tape contents, head position and current state
  4. Dthe property of a grammar that allows a string to have more than one parse tree or derivation
Show Answer
Correct Answer: C. a full snapshot of tape contents, head position and current state

Configuration of a Turing machine refers to a full snapshot of tape contents, head position and current state.

Q264 Turing Machines & Decidability

A correct statement about Configuration of a Turing machine is:

  1. Aa symbol that appears in final strings of the language
  2. Ba full snapshot of tape contents, head position and current state
  3. Can expression such as (a+b)*ab(a+b)* over {a,b}
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: B. a full snapshot of tape contents, head position and current state

Configuration of a Turing machine refers to a full snapshot of tape contents, head position and current state.

Q265 Turing Machines & Decidability

What is meant by TM for a^n b^n in Theory of Automata?

  1. Aa Turing machine strategy that repeatedly marks matching a's and b's
  2. Ba characterization of regular languages using finitely many equivalence classes of distinguishable strings
  3. Ca necessary property used to prove that some languages are not regular
  4. Da named condition or memory position of the machine
Show Answer
Correct Answer: A. a Turing machine strategy that repeatedly marks matching a's and b's

TM for a^n b^n refers to a Turing machine strategy that repeatedly marks matching a's and b's.

Q266 Turing Machines & Decidability

Which option best explains TM for a^n b^n?

  1. Aa definition that gives base strings and rules for generating more strings
  2. Ba Turing machine strategy that repeatedly marks matching a's and b's
  3. Ca non-accepting state that the machine cannot escape once entered
  4. Dthe expression (0+1)*, which represents every string over {0,1}
Show Answer
Correct Answer: B. a Turing machine strategy that repeatedly marks matching a's and b's

TM for a^n b^n refers to a Turing machine strategy that repeatedly marks matching a's and b's.

Q267 Turing Machines & Decidability

A correct statement about TM for a^n b^n is:

  1. Aa grammar symbol that cannot help derive any terminal string from the start variable
  2. Ban expression such as (0+1)*01 over the alphabet {0,1}
  3. Ca Turing machine strategy that repeatedly marks matching a's and b's
  4. DPDA acceptance that occurs when input is consumed and the machine is in an accepting state
Show Answer
Correct Answer: C. a Turing machine strategy that repeatedly marks matching a's and b's

TM for a^n b^n refers to a Turing machine strategy that repeatedly marks matching a's and b's.

Q268 Turing Machines & Decidability

What is meant by Decidability in Theory of Automata?

  1. Aa method that creates automaton states from grammar variables and transitions from productions
  2. Ba production of the form A→B where both sides are single variables
  3. Ca last-in first-out memory structure used by a pushdown automaton
  4. Dthe property that a problem has an algorithm that always halts with a yes or no answer
Show Answer
Correct Answer: D. the property that a problem has an algorithm that always halts with a yes or no answer

Decidability refers to the property that a problem has an algorithm that always halts with a yes or no answer.

Q269 Turing Machines & Decidability

Which option best explains Decidability?

  1. Aan expression such as (0+1)*01 over the alphabet {0,1}
  2. Ba formal system of variables, terminals, productions and a start symbol
  3. Ca PDA that pushes symbols for a's and pops them while reading b's
  4. Dthe property that a problem has an algorithm that always halts with a yes or no answer
Show Answer
Correct Answer: D. the property that a problem has an algorithm that always halts with a yes or no answer

Decidability refers to the property that a problem has an algorithm that always halts with a yes or no answer.

Q270 Turing Machines & Decidability

A correct statement about Decidability is:

  1. Aa PDA that pushes symbols for a's and pops them while reading b's
  2. Ba grammar in which at most one nonterminal appears at the right end of a production
  3. Cthe property that a problem has an algorithm that always halts with a yes or no answer
  4. Dthe theorem stating that regular expressions and finite automata define the same class of languages
Show Answer
Correct Answer: C. the property that a problem has an algorithm that always halts with a yes or no answer

Decidability refers to the property that a problem has an algorithm that always halts with a yes or no answer.

Q271 Turing Machines & Decidability

What is meant by Decision problem in Theory of Automata?

  1. Athe distinguished nonterminal from which derivation begins
  2. Ba problem whose answer is either yes or no
  3. Ca language that cannot be recognized by any finite automaton
  4. Dany set of strings formed from the symbols of that alphabet
Show Answer
Correct Answer: B. a problem whose answer is either yes or no

Decision problem refers to a problem whose answer is either yes or no.

Q272 Turing Machines & Decidability

Which option best explains Decision problem?

  1. Athe string obtained by writing the original symbols in the opposite order
  2. Ba problem whose answer is either yes or no
  3. Ca finite sequence of symbols chosen from an alphabet
  4. Da derivation that always replaces the leftmost nonterminal first
Show Answer
Correct Answer: B. a problem whose answer is either yes or no

Decision problem refers to a problem whose answer is either yes or no.

Q273 Turing Machines & Decidability

A correct statement about Decision problem is:

  1. Aa language that cannot be recognized by any finite automaton
  2. BPDA acceptance that occurs when input is consumed and the stack is emptied
  3. Ca snapshot showing current state, unread input and stack contents
  4. Da problem whose answer is either yes or no
Show Answer
Correct Answer: D. a problem whose answer is either yes or no

Decision problem refers to a problem whose answer is either yes or no.

Q274 Turing Machines & Decidability

What is meant by Decidable language in Theory of Automata?

  1. Aa grammar in which at most one nonterminal appears at the left end of a production
  2. Ban unbounded memory divided into cells that can hold symbols
  3. Ca language for which some Turing machine halts on every input and decides membership
  4. Dan operation that places a symbol on the top of the stack
Show Answer
Correct Answer: C. a language for which some Turing machine halts on every input and decides membership

Decidable language refers to a language for which some Turing machine halts on every input and decides membership.

Q275 Turing Machines & Decidability

Which option best explains Decidable language?

  1. Athe string obtained by writing the original symbols in the opposite order
  2. Ban expression such as (0+1)*01 over the alphabet {0,1}
  3. Ca language that cannot be recognized by any finite automaton
  4. Da language for which some Turing machine halts on every input and decides membership
Show Answer
Correct Answer: D. a language for which some Turing machine halts on every input and decides membership

Decidable language refers to a language for which some Turing machine halts on every input and decides membership.

Q276 Turing Machines & Decidability

A correct statement about Decidable language is:

  1. Aa language for which some Turing machine halts on every input and decides membership
  2. Ba language that cannot be recognized by any finite automaton
  3. Cthe problem of deciding whether a finite automaton accepts at least one string
  4. Da language that contains only a limited number of strings
Show Answer
Correct Answer: A. a language for which some Turing machine halts on every input and decides membership

Decidable language refers to a language for which some Turing machine halts on every input and decides membership.

Q277 Decision Problems

What is meant by FA emptiness problem in Theory of Automata?

  1. Aa problem whose answer is either yes or no
  2. Ba characterization of regular languages using finitely many equivalence classes of distinguishable strings
  3. Cthe problem of deciding whether a finite automaton accepts at least one string
  4. Da grammar in which at most one nonterminal appears at the right end of a production
Show Answer
Correct Answer: C. the problem of deciding whether a finite automaton accepts at least one string

FA emptiness problem refers to the problem of deciding whether a finite automaton accepts at least one string.

Q278 Decision Problems

Which option best explains FA emptiness problem?

  1. Aa tree representation showing how a string is derived from a grammar
  2. Bthe method of converting an NFA into an equivalent DFA using sets of NFA states
  3. Cthe problem of deciding whether a finite automaton accepts at least one string
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: C. the problem of deciding whether a finite automaton accepts at least one string

FA emptiness problem refers to the problem of deciding whether a finite automaton accepts at least one string.

Q279 Decision Problems

A correct statement about FA emptiness problem is:

  1. Aa symbol that appears in final strings of the language
  2. Bthe problem of deciding whether a finite automaton accepts at least one string
  3. Can abstract computational model with a tape, head, states and transition rules
  4. Da PDA that pushes symbols for a's and pops them while reading b's
Show Answer
Correct Answer: B. the problem of deciding whether a finite automaton accepts at least one string

FA emptiness problem refers to the problem of deciding whether a finite automaton accepts at least one string.

Q280 Decision Problems

What is meant by FA equivalence problem in Theory of Automata?

  1. Athe problem of deciding whether two finite automata accept exactly the same language
  2. Ba finite automaton equipped with a stack for recognizing context-free languages
  3. Ca state where the Turing machine stops computation
  4. Da tree representation showing how a string is derived from a grammar
Show Answer
Correct Answer: A. the problem of deciding whether two finite automata accept exactly the same language

FA equivalence problem refers to the problem of deciding whether two finite automata accept exactly the same language.

Q281 Decision Problems

Which option best explains FA equivalence problem?

  1. Aa symbol that appears in final strings of the language
  2. Ban operation that removes the top symbol from the stack
  3. Cthe problem of deciding whether two finite automata accept exactly the same language
  4. Da language that contains only a limited number of strings
Show Answer
Correct Answer: C. the problem of deciding whether two finite automata accept exactly the same language

FA equivalence problem refers to the problem of deciding whether two finite automata accept exactly the same language.

Q282 Decision Problems

A correct statement about FA equivalence problem is:

  1. Athe property that a problem has an algorithm that always halts with a yes or no answer
  2. Bthe part of a Turing machine that reads, writes and moves on the tape
  3. Can unbounded memory divided into cells that can hold symbols
  4. Dthe problem of deciding whether two finite automata accept exactly the same language
Show Answer
Correct Answer: D. the problem of deciding whether two finite automata accept exactly the same language

FA equivalence problem refers to the problem of deciding whether two finite automata accept exactly the same language.

Q283 Chomsky Normal Form

What is meant by Chomsky Normal Form in Theory of Automata?

  1. Aa finite automaton equipped with a stack for recognizing context-free languages
  2. Ba CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  3. Ca directed labeled graph used to represent language recognition paths
  4. Da derivation that always replaces the rightmost nonterminal first
Show Answer
Correct Answer: B. a CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol

Chomsky Normal Form refers to a CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol.

Q284 Chomsky Normal Form

Which option best explains Chomsky Normal Form?

  1. Aa CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  2. Ba rule that writes a symbol, moves the head and changes state
  3. Can abstract computational model with a tape, head, states and transition rules
  4. Da postfix notation in which the operator is written after its operands
Show Answer
Correct Answer: A. a CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol

Chomsky Normal Form refers to a CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol.

Q285 Chomsky Normal Form

A correct statement about Chomsky Normal Form is:

  1. Aa CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol
  2. Ba directed labeled graph used to represent language recognition paths
  3. Ca finite automaton with exactly one next state for each state and input symbol
  4. Dthe rule that tells the automaton which state to move to after reading a symbol
Show Answer
Correct Answer: A. a CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol

Chomsky Normal Form refers to a CFG form where productions are of the form A→BC or A→a, with limited allowance for the start symbol.

Q286 Chomsky Normal Form

What is meant by Null production in Theory of Automata?

  1. Aan expression such as (0+1)*01 over the alphabet {0,1}
  2. Ba production that derives the empty string
  3. Can operation that allows zero or more repetitions of a language
  4. Da tabular representation of state changes for each input symbol
Show Answer
Correct Answer: B. a production that derives the empty string

Null production refers to a production that derives the empty string.

Q287 Chomsky Normal Form

Which option best explains Null production?

  1. Aa production that derives the empty string
  2. Ba process that removes null, unit and useless productions and converts long rules into binary form
  3. Cthe classic nonregular language containing equal numbers of a's followed by b's
  4. Da language that cannot be recognized by any finite automaton
Show Answer
Correct Answer: A. a production that derives the empty string

Null production refers to a production that derives the empty string.

Q288 Chomsky Normal Form

A correct statement about Null production is:

  1. Athe ability of a PDA to choose among multiple valid transitions
  2. Ban operation that places strings from one language directly after strings from another
  3. Ca process that removes null, unit and useless productions and converts long rules into binary form
  4. Da production that derives the empty string
Show Answer
Correct Answer: D. a production that derives the empty string

Null production refers to a production that derives the empty string.

Q289 Chomsky Normal Form

What is meant by Nullable variable in Theory of Automata?

  1. Aa finite automaton with exactly one next state for each state and input symbol
  2. Ba variable that can derive the empty string
  3. Ca process that removes null, unit and useless productions and converts long rules into binary form
  4. Da Turing machine strategy that repeatedly marks matching a's and b's
Show Answer
Correct Answer: B. a variable that can derive the empty string

Nullable variable refers to a variable that can derive the empty string.

Q290 Chomsky Normal Form

Which option best explains Nullable variable?

  1. Athe string with length zero, usually denoted by ε or lambda
  2. Bany string of terminals and nonterminals produced during a derivation
  3. Ca variable that can derive the empty string
  4. Da language generated by some context-free grammar
Show Answer
Correct Answer: C. a variable that can derive the empty string

Nullable variable refers to a variable that can derive the empty string.

Q291 Chomsky Normal Form

A correct statement about Nullable variable is:

  1. Aa variable that can derive the empty string
  2. Ba production of the form A→B where both sides are single variables
  3. Ca grammar in which at most one nonterminal appears at the left end of a production
  4. Da production that derives the empty string
Show Answer
Correct Answer: A. a variable that can derive the empty string

Nullable variable refers to a variable that can derive the empty string.

Q292 Chomsky Normal Form

What is meant by Unit production in Theory of Automata?

  1. Aa directed labeled graph used to represent language recognition paths
  2. Ba finite-state machine whose output depends on the current state and input symbol
  3. Ca production of the form A→B where both sides are single variables
  4. Da named condition or memory position of the machine
Show Answer
Correct Answer: C. a production of the form A→B where both sides are single variables

Unit production refers to a production of the form A→B where both sides are single variables.

Q293 Chomsky Normal Form

Which option best explains Unit production?

  1. Aa method that creates automaton states from grammar variables and transitions from productions
  2. Ba process that removes null, unit and useless productions and converts long rules into binary form
  3. Cthe method of converting an NFA into an equivalent DFA using sets of NFA states
  4. Da production of the form A→B where both sides are single variables
Show Answer
Correct Answer: D. a production of the form A→B where both sides are single variables

Unit production refers to a production of the form A→B where both sides are single variables.

Q294 Chomsky Normal Form

A correct statement about Unit production is:

  1. APDA acceptance that occurs when input is consumed and the machine is in an accepting state
  2. Ban expression such as a(a+b)* over the alphabet {a,b}
  3. Ca production of the form A→B where both sides are single variables
  4. Dthe state from which computation begins
Show Answer
Correct Answer: C. a production of the form A→B where both sides are single variables

Unit production refers to a production of the form A→B where both sides are single variables.

Q295 Chomsky Normal Form

What is meant by Useless symbol in Theory of Automata?

  1. Aa finite-state machine whose output depends only on the current state
  2. Ba grammar symbol that cannot help derive any terminal string from the start variable
  3. Ca derivation that always replaces the leftmost nonterminal first
  4. Dan abstract computational model with a tape, head, states and transition rules
Show Answer
Correct Answer: B. a grammar symbol that cannot help derive any terminal string from the start variable

Useless symbol refers to a grammar symbol that cannot help derive any terminal string from the start variable.

Q296 Chomsky Normal Form

Which option best explains Useless symbol?

  1. Athe method of converting an NFA into an equivalent DFA using sets of NFA states
  2. Ba production of the form A→B where both sides are single variables
  3. Ca grammar symbol that cannot help derive any terminal string from the start variable
  4. Da language that contains only a limited number of strings
Show Answer
Correct Answer: C. a grammar symbol that cannot help derive any terminal string from the start variable

Useless symbol refers to a grammar symbol that cannot help derive any terminal string from the start variable.

Q297 Chomsky Normal Form

A correct statement about Useless symbol is:

  1. Aa grammar with productions restricted to right-linear or left-linear form
  2. Bthe expression (0+1)*, which represents every string over {0,1}
  3. Ca grammar symbol that cannot help derive any terminal string from the start variable
  4. Da necessary property used to prove that some languages are not regular
Show Answer
Correct Answer: C. a grammar symbol that cannot help derive any terminal string from the start variable

Useless symbol refers to a grammar symbol that cannot help derive any terminal string from the start variable.

Q298 Chomsky Normal Form

What is meant by CNF conversion in Theory of Automata?

  1. Aa process that removes null, unit and useless productions and converts long rules into binary form
  2. Ba prefix notation in which the operator is written before its operands
  3. Can alphabet whose symbols are clearly defined and can be used to build strings
  4. Da rewriting rule that replaces one symbol or pattern with another string
Show Answer
Correct Answer: A. a process that removes null, unit and useless productions and converts long rules into binary form

CNF conversion refers to a process that removes null, unit and useless productions and converts long rules into binary form.

Q299 Chomsky Normal Form

Which option best explains CNF conversion?

  1. Aa tree representation showing how a string is derived from a grammar
  2. Ba process that removes null, unit and useless productions and converts long rules into binary form
  3. Ca non-accepting state that the machine cannot escape once entered
  4. Da language that contains only a limited number of strings
Show Answer
Correct Answer: B. a process that removes null, unit and useless productions and converts long rules into binary form

CNF conversion refers to a process that removes null, unit and useless productions and converts long rules into binary form.

Q300 Chomsky Normal Form

A correct statement about CNF conversion is:

  1. Aa language containing no strings at all
  2. Ba process that removes null, unit and useless productions and converts long rules into binary form
  3. Ca formal system of variables, terminals, productions and a start symbol
  4. Da language for which some Turing machine halts on every input and decides membership
Show Answer
Correct Answer: B. a process that removes null, unit and useless productions and converts long rules into binary form

CNF conversion refers to a process that removes null, unit and useless productions and converts long rules into binary form.

Join ElecturesAI Updates

For more MCQs, notes and learning updates, join the WhatsApp channel or contact us directly.

WhatsApp Channel: https://whatsapp.com/channel/0029VbCBele72WU5CJvllA0p
WhatsApp: Chat on WhatsApp

WhatsApp
© ElecturesAI — Smart MCQ Practice

Animal Diversity-II Chordates MCQs with Answers

Share with love!

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *