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

Automata Theory and Formal Language

Showing 151-225 of 246 answers

Let w = 100011, is w a member of a language of string with equal number of 0s and 1s?
  • Yes, because the number of 1s is the same as the number of 0s, which is 3 Correct
  • It is hard to ascertain because 100011 is 35 in decimal, which is an odd number
  • No, because even if the symbols 1 and 0 are of the same number, they are not palindromic
  • This is an NP-hard problem
NFA means:
  • Nondeterministic Finite Automaton Correct
  • Nondeterministic Final Automaton
  • Nondifferentiable Final Automaton
  • Nondifferential Finite Automaton
Noam Chomsky gave a mathematical model in _______ which is effective for writing computer languages.
  • 1956 Correct
Non-terminal symbols
  • S & A Correct
NP-Hard problems are problems that are...
  • Easy (they are called hard so that computer programmers can be paid more)
  • intractable Correct
  • none of the choices
  • hard
Number of final state require to accept in minimal finite automata.
  • None of the mentioned Correct
Number of states require to accept string ends with 10.
  • 3 Correct
One of the first programmable electronic computers in 1945.
  • ENIAC Correct
Production Rule: aAb->agb belongs to which of the following category?
  • Context Sensitive Language Correct
Recursive : TM that always halt = ________________ : TM that may or may not halt
  • iterative
  • recursively enumerable Correct
  • none of the choices given
  • iteratively enumerable
Regular expression Φ* is equivalent to.
  • ϵ Correct
Regular sets are closed under union,concatenation and kleene closure.
  • TRUE Correct
S → aAb, aA →aaAb, A→ε
  • P Correct
Set of all tape symbols
  • Γ Correct
Set of final or accepting states.
  • F Correct
Some graphs contain cycles.
  • True Correct
  • False
Start symbol, S ∈ N
  • S Correct
Starting state
  • q0 Correct
T generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars.
  • Type-0 grammars Correct
Terminal symbols
  • a & b Correct
The _____ of two sets A and B is the set containing those elements which are elements of A or elements of B.
  • union Correct
The __________ of a Turing machine depends on the current state of finite control and the tape symbol present in the input tape.
  • single move Correct
The algebraic law of regular expression described by E + E = E is _____________.
  • Annihilator
  • Identity
  • Additive idempotent
  • Idempotent Correct
The algebraic law of regular expression described by φE = φ = Eφ is _______________.
  • Annihilator Correct
  • Associative
  • Commutative
  • Identity
The basic model of a Turing machine consists of _______ and _______ , in which the finite control has finite set of states and the transition between the states.
  • finite control, input tape Correct
The body of a production in CFG is composed of:
  • a string of terminals only
  • none of the choices given because a CFG production does not have a body
  • a string of non-terminals only
  • a string of terminals and non-terminals Correct
The cardinality of the union of two disjoint sets is less than the sum of the cardinality of the given sets.
  • True Correct
  • False
The CFG "S → (S) | SS | ε" accepts:
  • the string "<<>><><<>>"
  • the string "(((((((((())))))))))"
  • the string "((()))(())(())" Correct
  • the string "{} { {} } [[]]"
The commutativity property of set operations states that the union of any set with same set is the set itself.
  • True
  • False Correct
The complement of an infinite language is necessarily finite.
  • FALSE Correct
The difference between DFA and NFA
  • DFA is where you get your passport while NFA is where you get your cheap rice
  • NFA can exist in only one state at a given time while DFA can exist in multiple states
  • DFA can exist in only one state at a given time while NFA can exist in multiple states Correct
  • DFA is also an NFA
The difference between regular expressions and finite automata is _____________.
  • that automata are more program syntax-like while regular expression are more machine-like
  • |regular expression| - |finite automata| = |Turing Machine| because you can only get the difference by computing for their respective lengths
  • that regular expressions are more program syntax-like while automata are more machine-like Correct
  • {regular expression} - {finite automata} = { } because they are sets and they are equivalent
The empty set is always a subset of any set.
  • True Correct
  • False
The entity which generate Language is termed as regular languages.
  • FALSE Correct
The entity which generate Language is termed as:
  • Grammar Correct
The first counting machine developed 5000 years ago in the Middle East.
  • Abacus Correct
The first mechanical calculator using gears for calculation developed in 1642.
  • Pascaline Correct
The following are phases of C++ Programs except
  • Process Correct
The initial stack top symbol (I ∈ S).
  • I Correct
The initial state (q0 ∈ Q)
  • q0 Correct
The intersection of sets A and B is expressed as _________________.
  • A - B
  • A / B
  • A x B
  • A ∩ B Correct
The language L contains all strings over the alphabet {a,b} that begin with and end with
  • a,b Correct
The minimum number of states required to recognize an octal number divisible by 3 are/is.
  • 3 Correct
The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is
  • 7 Correct
The PDA has infinite memory and access in _____ order and the finite automata has ____ memory.
  • LIFO, finite Correct
The power set of a given set does not contain the set itself.
  • True
  • False Correct
The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
  • TRUE Correct
The relationship between recursive and recursively enumerable languages is ________________.
  • ∈
  • ⊂ Correct
  • ∉
  • ⊃
The stack content
  • s Correct
The stack contents
  • s Correct
The start symbol.
  • S Correct
The string "0000111" is accepted by _____________.
  • the CFG S → 0S1 | A, A → A1 | ε
  • the CFG S → 1S0 | A, A → A0 | ε
  • the CFG S → 0S1 | A, A → 0A | ε Correct
  • none of the choices
The string aaaabbbccaaad is accepted by this regular expression.
  • a+b+c+d+
  • a*b*c*a*d*e+
  • a*b*c*a*d* Correct
  • a+b+c+d+e*
The string abe is accepted by this regular expression.
  • a*b*c*a*d*
  • a+b+c+d+e*
  • a*b*c*a*d*e+ Correct
  • a+b+c+d+
The string acde is accepted by this regular expression.
  • a+b+c+d+
  • a+b+c+d+e*
  • a*b*c*a*d*
  • a*b*c*a*d*e+ Correct
The symbol used for the empty string is ____________.
  • ε Correct
  • φ
  • a blank
  • ψ
The tape head is positioned at one of the tape cells for scanning the input symbol from the input tape and initially the tape head points at the left most cell of the input tape.
  • TRUE Correct
The theory of formal languages finds its applicability extensively in the fields of Computer Science. gave a mathematical model of grammar in which is effective for writing computer languages.
  • Noam Chomsky, 1956 Correct
The top symbol is read and removed.
  • Pop Correct
The transition a Push down automaton makes it additionally dependent upon the _____.
  • stack Correct
The unconsumed input.
  • w Correct
The union of sets A and B is expressed as?
  • A U B Correct
  • A - B
  • A / B
  • A x B
There are 5 tuples in finite state machine.
  • TRUE Correct
Transition function
  • δ Correct
Turing hypothesis believed that a function is said to be computable if and only if it can be computed by a Turing machine.
  • FALSE Correct
Unconsumed input
  • w Correct
What are strings?
  • A string is an infinite area of symbols chosen from Σ
  • A string is a finite sequence of symbols chosen from Σ Correct
  • A string is a finite area of symbols chosen from Σ
  • A string is an infinite sequence of symbols chosen from Σ
What can be said about CFLs?
  • It is closed under ~
  • It is closed under ∩
  • All of the given choices
  • It is closed under • Correct
What can be said about undecidable problems?
  • They are definitely recursive
  • They are surely iterative
  • They are not recursive Correct
  • They are not iterative
What can not be said about CFLs?
  • It is closed under ~
  • It is closed under — Correct
  • All of the given choices
  • It is closed under ∩
What cannot be said about automata theory?
  • None of the choices Correct
  • Automata theory is the study of abstract computing devices or machines
  • Automata theory is used to find out if a problem is computable
  • Automata theory answers the fundamental questions in computer science
What concept did Alan Turing introduce?
  • The concept of programs and programmabilities of problems
  • The concept of decidability Correct
  • The concept of functions and relations
  • The concept of undecidability
What is a grammar?
  • How a sentence should be constructed to avoid syntax error
  • "Them cowboys is dumb!" is an example of a wrong grammar
  • "We ain't gonna make mistakes" is an example of correct grammar
  • A device that enumerates the sentences of a language Correct
What is a language?
  • A way to communicate with other humans
  • A collection of finite-length sentences that were constructed from a finite set of symbols Correct
  • A code that you use when writing a computer program
  • English, Filipino and Valyrian are examples of a language
What is a Universal TM?
  • a TM that stimulates another TM Correct
  • A TM that can solve all problems
  • A TM that can solve all undecidable problems
  • a Universal TM does not exist
This course is taught by the mentor:
Professor Paul Jacob Cruz

Paul Jacob Cruz

Master of Science in Computer Science.

All courses