Your browser does not support JavaScript!
AMA University Answers
Login Register

Automata Theory and Formal Language

Showing 76-150 of 246 answers

Any production rule in the form A → B where A, B ∈ Non-terminal is called unit production.
  • Unit Production Correct
Any production rule in the form A → B where A, B ∈ Non-terminal is called.
  • Unit Production Correct
Any set that represents the value of the Regular Expression is called a Property set.
  • FALSE Correct
Are ambiguous grammar context free?
  • TRUE Correct
are parameterized statement, they are true or false depending on the values of their parameters.
  • predicates Correct
Blank symbol
  • Δ Correct
challenged the mathematical community to find an infallible, mechanical method for constructing and checking truth of mathematical statements.
  • David Hilbert Correct
Checking whether there is a matching parenthesis in a computer code can be done by a ______________.
  • regular expression
  • automatically by a very patient debugger
  • context-free language
  • context-free grammar Correct
Circuits in graphs are always simple paths.
  • True Correct
  • False
Computer science has roots in two fields :
  • Mathematics Correct
Computers are general purpose because they can perform many different tasks.
  • TRUE Correct
Connected graphs have components.
  • True
  • False Correct
Context Free Languages is closed under intersection.
  • False Correct
  • True
Context-free grammars are more expressive than finite automata; if a language L is _____ by a finite automata then L can be _______ by a context-free grammar.
  • accepted, generated Correct
Context-free grammars are more expressive than finite automata; if a language L is by a finite automata then L can be blank by a context-free grammar.
  • Accepted Correct
Context-free grammars are more expressive than finite automata; if a language L is by a finite automata then L can be by a context-free grammar.
  • Accepted, Ignored Correct
Elimination of productions and symbols is called simplification of CFGs. Simplification essentially comprises of the following steps:
  • Reduction of CFG Correct
Empty set is a/an ________________.
  • Infinite set
  • Finite set Correct
  • Invalid set
  • None of the choices
Empty string
  • Σ Correct
Every context free grammar can be transformed into an equvalent non deterministic push down automata.
  • TRUE Correct
Every set is a / an ________________ of itself.
  • None of the choices
  • Complement
  • Proper Subset
  • Improper Subset Correct
Finite Automata all regular languages and only regular languages.
  • Accept Correct
Finite set of input alphabets.
  • Σ Correct
Finite set of states
  • Q Correct
For a regular expression 'a', we can construct the following FA:
  • TRUE Correct
For bottom-up parsing, a PDA has the following four types of transitions:
  • Push the current input symbol into the stack., Replace the right‑hand side of a production at the top of the stack with its left‑hand side. , If the top of the stack element matches with the current input symbol, pop it. , If the input string is fully read and only if the start symbol 'S' remains in the stack, pop it and go to the final state . Correct
For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
  • TRUE Correct
For every pair of regular expressions R and S, the languages denoted by R(SR)* and (RS)*R are the same.
  • TRUE Correct
For the given Regular expression, the minimum number of terminals required to derive its grammar (011+1)*(01)* is
  • 3,6,2,5,4 Correct
Given that the language L = {ε}, is L empty?
  • None of the given choices
  • No, because the language has an empty symbol Correct
  • Definitely, because ε is an empty symbol
  • This is a case of apples and oranges, you really can't compare!
Given the language L = {ε}, is L empty?
  • none of the given choices
  • Definitely, because ε is an empty symbol
  • No, because the language has an empty symbol Correct
  • You can't say
Given the productions S → αXβ, X → a, ___________________.
  • X is not reachable nor generating
  • X is reachable but not generating
  • X is useful  Correct
  • X is not reachable but is generating
Global Positioning System (GPS) calculates latitude and longitude from satellite signals.
  • True Correct
Having the initial state as a final state, give the deterministic finite state automaton that accepts the regular expression.
  • ((a.b)+c)* Correct
How many rational and irrational numbers are possible between 0 and 1?
  • 0
  • Infinite Correct
  • Finite
  • 1
How many sets belong to the power set of A = {a,b,c,d}?
  • 4
  • 8
  • 7
  • 16 Correct
Identify the modeling recognition of the word "then"
  • Start State Correct
If A →* ε, then we can say that:
  • A is not generating
  • A is not reachable
  • A is nullable Correct
  • A is not generally useful
If A = {0,2) and B = {1,3), then Cartesian product is?
  • none of the choices
  • A x B not equal B x A Correct
  • A x B = B x A
  • is not possible 
If A = {3, 4, 6, 8} and
  • { 4,6} Correct
If A = {5,6,7} and B = {7,8,9} then A U B is equal to:
  • {5,6,7}
  • None of the choices
  • {7,8,9}
  • {5,6,7,8,9} Correct
If A has m elements and B has n elements, then A x B has elements?
  • m - n
  • m + n
  • 2n
  • m x n Correct
If a problem can be shown that it belongs to the class of recursively enumerable languages then ______________________.
  • It may be solved by any TM Correct
  • It may be solved by a special RE
  • It may be solved by a special TM
  • It may be solved by any RE
If L is recursively enumerable then ________________.
  • none of the choices given is correct
  • L is also recursively enumerable
  • L is definitely not recursively enumerable
  • L may not be recursively enumerable Correct
If L1 and L2 are regular sets then intersection of these two will be.
  • Regular Correct
If R = {(1,1),(2,3),(4,5)}, then domain of the function is?
  • Dom R = {2,3,4,5}
  • Dom R = {1,2,4} Correct
  • Dom R {1,3,5}
  • Dom R {1,1,4,5}
If R ={(1,1),(2,3),(4,5)}, then the Range of the function is?
  • Range R {1,1,4,5}
  • Range R {1,2,5}
  • Range R = {2,3,4,5}
  • Range R = {1,3,5} Correct
If we can successfully and correctly stimulate a TM with storage by two standard TMs, then ______________________.
  • None of the choices
  • we have already shown that the TM with storage is at least twice as powerful as one standard TM
  • we have already shown that the two are equivalent Correct
  • we have already shown that one standard TM is half as powerful as the TM with storage
If we can successfully and ly stimulate a TM with storage by two standard TMs, then ______________________
  • we have already shown that the two are equivalent Correct
If Σ2 is {00, 01, 10, 11}, then Σ =
  • {0, 1} Correct
  • {false, true}
  • {true, false}
  • {F, T}
In Allan M. Turing proposed the Turing machine as a model of "any possible computation".
  • 1936 Correct
In mathematical notation, the symbol → means...
  • implication Correct
  • an element of
  • not an element of 
  • assignment statement
In the Chomsky Hierarchy:
  • Regular Language ⊂ Context-sensitive Language  Correct
  • Regular Language ⊃ Context-sensitive Language 
  • Regular Language| • |Context-sensitive Language 
  • Regular Language = Context-sensitive Language 
In words, H → C means…
  • Whenever H holds, C follows Correct
  • Whenever H does not follow, C does not follow either
  • Whenever H is true, then it becomes C
  • Whenever H, then it becomes C
Increasing accuracy, or precision
  • Minimizing False Positives Correct
Increasing coverage, or recall.
  • Minimizing False Negatives Correct
Is a set of final state/states of Q (F ⊆ Q).
  • F Correct
Is the transition function where δ: Q × Σ → Q.
  • δ Correct
Is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.
  • Pumping Lemma Correct
Is used to derive a string using the production rules of a grammar.
  • Production Correct
It generate context-free languages. The productions must be in the form A → γ
  • Type-2 grammars Correct
IT generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars.
  • Type-0 grammars Correct
IT generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars. They generate the languages that are recognized by a Turing machine.
  • Type-0 grammars Correct
It is a unary operator on a set of symbols or strings, that gives the infinite set of all possible strings of all possible lengths.
  • Σ * Correct
It process information in their efforts to eat, survive, and reproduce.
  • Living Organisms Correct
It refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.
  • Time Complexity Correct
It starts from the bottom with the string and comes to the start symbol using a parse tree.
  • Bottom-Up Parser Correct
It starts from the top with the start-symbol and derives a string using a parse tree.
  • Top-Down Parser Correct
JASON can generally be parsed by ______________.
  • A C parser
  • A CFG Correct
  • A Java parser
  • A RE
Labeled by a non-terminal symbol.
  • Vertex Correct
Labeled by a terminal symbol or ε.
  • Leaves Correct
Labeled by the start symbol.
  • Root Vertex Correct
Language may be derived from other strings using the productions in a grammar.
  • FALSE Correct
Leibniz introduced binary notation of calculation.
  • FALSE Correct
Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then.
  • L1=L2 Correct
This course is taught by the mentor:
Professor Paul Jacob Cruz

Paul Jacob Cruz

Master of Science in Computer Science.

All courses