Your browser does not support JavaScript!

Automata Theory and Formal Language

Showing 1-75 of 246 answers

__ is a finite set of states.
  • Q Correct
__ is a finite set of symbols called the alphabet.
  • Σ Correct
__ is the initial state from where any input is processed (q0 ∈ Q).
  • q0 Correct
______ is used to derive a string using the production rules of a grammar.
  • Parsing Correct
“C if H” is also the same as saying _______.
  • “If H then ” Correct
  • “If C then H”
  • “If H then C else {}”
  • “If H then C else do nothing”
“If H then ” is also the same as saying _______.
  • “If H then C else do nothing”
  • “If C then H”
  • “If H then C else {}”
  • “C if H” Correct
“Whenever H holds, C follows” can also be said as _______.
  • H → ε and  ε → C
  • H → C Correct
  • C → H
  • ε → H and  C →  ε
{Q, Σ, q0, F, δ, Q × Σ → Q} is…
  • An NFA
  • Either DFA or NFA
  • There is no such tuple Correct
  • A DFA
* Starts from tree leaves. It proceeds upward to the root which is the starting symbol S.
  • Bottom-Up Approach Correct
* Starts with the starting symbol S. It goes down to tree leaves using productions.
  • Top-Down Approach Correct
|-* is the _____ closure of |-
  • transitive and reflexive Correct
A __________ of a derivation is a tree in which each internal node is labeled with a nonterminal.
  • parse tree Correct
A - B will contain elements in?
  • B not in A
  • A not in B Correct
  • Neither A nor B
  • Both A and B
A ⊂ B is read as ________________.
  • A is less than B
  • A is a subset of B
  • B is a subset of A
  • A is a proper subset of B Correct
A 2-Tape Turing Machine ___________________.
  • can infer that recursive languages are closed under union
  • can show that recursive languages are closed under union Correct
  • has two outputs
  • has two inputs
A compact textual representation of a set of strings representing a language.
  • Regular Expressions Correct
A conceptual design for a machine consisting of a Mill, Store, Printer, and Readers.
  • Analytic Engine Correct
A DFA can remember a finite amount of information, but a can remember an infinite amount of information.
  • PDA Correct
A DFA is defined ____________________.
  • as Department of Finite Automaton
  • by a 5-tuple which is {Q, Σ, q0, F, δ} Correct
  • by a 6-tuple which is {Q, Σ, q0, F, δ, Q × Σ → Q}
  • as Department of Foreign Affairs
A DFA is represented by digraphs called.
  • State Diagram Correct
A DPDA is a PDA in which
  • No state p has two outgoing transitions Correct
A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the alphabet set but also without any input symbol. This transition without input is called a
  • Null Move Correct
A finite number of states.
  • Q Correct
A finite set of input symbols.
  • Σ Correct
A finite set of states
  • Q Correct
A formal language is a set of strings, each string composed of symbols from a finite set called.
  • Alphabet Correct
A general purpose, programmable, information processor with input and output.
  • computer Correct
A good regular expression for any valid real number using engineering notation is ______________.
  • [0-9]+[0-9]*[(E|e)[0-9]+] Correct
  • [0-9]*
  • [0-9]+[0-9]*[(E|e|∈)[0-9]+]
  • [0-9]+
A good regular expression for any valid whole number is ______________.
  • [0-9]*
  • [0-9]*[0-9]*
  • [0-9]+ Correct
  • [0-9]+[0-9]*
A good regular expression of a person's name is ______________.
  • None of the given choices
  • [A-Z][a-z]+
  • [A-Z][a-z]?
  • [A-Z][a-z]* Correct
A grammar G is ambiguous if there is a word w Î L(G) having are least two different parse trees.
  • TRUE Correct
A language accepted by Deterministic Push down automata is closed under which of the following?
  • complement Correct
A language is regular if and only if.
  • Accepted by DFA Correct
A may or may not read an input symbol, but it has to read the top of the stack in every transition.
  • PDA Correct
A Moore machine can be described by a tuple.
  • 6 Correct
A nested if-then statement is one of these:
  • If w then x if y then z
  • If w if x then y then z
  • If w then if x then y else z Correct
  • All of the choices are examples of nestedness
A new symbol is added at the top.
  • Push Correct
A parsing that starts from the top with the start-symbol and derives a string using a parsetree.
  • top-down parser Correct
A PDA accepts a string when, after reading the entire string, the PDA is in a final state.
  • TRUE Correct
A PDA is already in its accept state if:
  • and only if it is both in the final state and the stack is empty
  • none of the given choices
  • it is either in the final state or the stack is empty Correct
  • it has no more input to process
A PDA machine configuration (p, w, y) can be correctly represented as.
  • Current state, Unprocessed input, Stack content Correct
A PDA machine configuration (p, w, y) can be ly represented as ____________
  • current state, unprocessed input, stack content Correct
A pushdown automata can be regarded as:
  • a ε-NFA with a stack Correct
  • a DFA with a FILO queue
  • a NFA with a stack
  • a DFA with FIFO queue
A pushdown automaton is a way to implement a context-free grammar in a similar way to design DFA for a regular grammar.
  • TRUE Correct
A regular expression consisting of a finite set of grammar rules is a quadruple.
  • FALSE Correct
A right-most derivation of a sentential form is one in which rules transforming the are always applied.
  • Context Correct
A set has n elements, then the number of elements in its power set is?
  • 2n
  • 2 ^ n Correct
  • None of the choices
  • 2n-1
A set of accepting states (F ∈ Q).
  • F Correct
A set of final state/states of Q (F⊆Q).
  • F Correct
A set of rules, P: N → (N U T)*, it does have any right context or left context.
  • P Correct
A set of strings of a's and b's of any length including the null string. So L= { ε, a, b, aa , ab , bb , ba, aaa.......}, the regular
  • (a+b)* Correct
A set of strings of a's and b's of any length including the null string. So L= { ε, a, b, aa , ab , bb , ba, aaa.......}, the regular expression is.
  • (a+b)* Correct
A set of terminals where N ∩ T = NULL.
  • T Correct
A set on non-terminal symbols.
  • S & A Correct
A stack symbols
  • Σ Correct
A string is accepted by a, iff the DFA/NDFA starting at the initial state ends in an after reading the string.
  • NDFA Correct
A sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the
  • Partial Derivation Tree, Sub-Tree Correct
A symbol X is reachable _________________________.
  • if S → aXβ
  • if X →* w, for some w ∈ Σ
  • if X → w, for some w ∈ Σ
  • if S →* aXβ Correct
A transition function δ : Q × (Σ ∪ {ε}) → 2Q.
  • δ Correct
A transition function: Q × (Σ∪{ε}) × S × Q × S*.
  • δ Correct
A' will contain how many elements from the original set A?
  • 1
  • all elements in A
  • infinite
  • 0 Correct
According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F} Statement 1: q ϵ Q'; Statement 2: FϵQ
  • Statement 1 is false, Statement 2 is true Correct
According to what concept is CFL a superset of RL?
  • Chomsky Hierarchy Correct
  • Chomsky Normal Form
  • Backus-Naur Form
  • None of the given choices
All functions are relations
  • True Correct
  • False
All relations are functions
  • True
  • False Correct
All trees contain loops.
  • True
  • False Correct
An algorithms to shampoo your hair.
  • rinse, lather, repeat Correct
An alphabet is any finite set of symbols.
  • TRUE Correct
An automaton that produces outputs based on current input and/or previous state is called.
  • Transducer Correct
An English like abbreviations representing elementary computer operations.
  • Assembly Language Correct
An example string w of a language L characterized by equal number of As and Bs is _______________.
  • ABBBAA Correct
An indirect way of building a CFG is to _____________
  • build a regular expression and then construct a PDA from it, and then construct CDF from it
  • You can only build a CFG directly
  • build a PDA and then construct a CFG from it Correct
  • none of the given choices
An initial state q0 ∈ Q
  • q0 Correct
An order rooted tree that graphically represents the semantic information a string derived from a context-free grammar.
  • Derivation tree Correct
An ε-NFA with a stack is also regarded as:
  • A CFG
  • A FSA
  • A PDA Correct
  • A RE
This course is taught by the mentor:
Professor Paul Jacob Cruz

Paul Jacob Cruz

Master of Science in Computer Science.

All courses