Automata Theory and Formal Language

CS 6205 Automata Theory and Formal Language

A DFA can remember a finite amount of information, but a ____ can remember an infinite amount of information.	PDA
A DFA can remember a finite amount of information, but a can remember an infinite amount of information.	PDA
A DFA is defined ____________________.	by a 5-tuple which is {Q, Σ, q0, F, δ}
A DFA is represented by digraphs called.	State Diagram
A DPDA is a PDA in which	No state p has two outgoing transitions
A DPDA is a PDA in which.	No state p has two outgoing transitions
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
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
A finite number of states	Q
A finite number of states.	Q
A finite set of input symbols.	Σ
A finite set of states	Q
A finite set of states.	Q
A formal language is a set of strings, each string composed of symbols from a finite set called	alphabet
A formal language is a set of strings, each string composed of symbols from a finite set called.	Alphabet
A general purpose, programmable, information processor with input and output.	computer
A good regular expression for any valid real number using engineering notation is ______________.	[0-9]+[0-9]*[(E|e)[0-9]+]
A good regular expression for any valid whole number is ______________.	[0-9]+
A good regular expression of a person's name is ______________.	[A-Z][a-z]*
A grammar G is ambiguous if there is a word w Î L(G) having are least two different parse trees.	TRUE
A language accepted by Deterministic Push down automata is closed under which of the following?	complement
A language is regular if and only if.	Accepted by DFA
A may or may not read an input symbol, but it has to read the top of the stack in every transition	PDA
A may or may not read an input symbol, but it has to read the top of the stack in every transition.	PDA
A Moore machine can be described by a tuple.	6
A nested if-then statement is one of these:	If w then if x then y else z
A new symbol is added at the top.	Push
A of a derivation is a tree in which each internal node is labeled with a nonterminal.	Parse Tree
A parsing that starts from the top with the start-symbol and derives a string using a parsetree.	top-down parser
A PDA accepts a string when, after reading the entire string, the PDA is in a final state.	TRUE
A PDA is already in its accept state if:	it is either in the final state or the stack is empty
A PDA machine configuration (p, w, y) can be ly represented as ____________ .	current state, unprocessed input, stack content
A PDA machine configuration (p, w, y) can be ly represented as.	Current state, Unprocessed input, Stack content
A pushdown automata can be regarded as:	a ε-NFA with a stack
A pushdown automaton is a way to implement a context-free grammar in a similar way to design DFA for a regular grammar.	TRUE
A regular expression consisting of a finite set of grammar rules is a quadruple.	FALSE
A right-most derivation of a sentential form is one in which rules transforming the are always applied.	Context
A set has n elements, then the number of elements in its power set is?	2 ^ n
A set of accepting states (F ∈ Q)	F
A set of accepting states (F ∈ Q).	F
A set of final state/states of Q (F⊆Q).	F
A set of rules, P: N → (N U T)*, it does have any right context or left context.	P
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)*
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)*
A set of terminals where N ∩ T = NULL.	T
A set on non-terminal symbols.	N
A stack symbols	Σ
A string is accepted by a, iff the DFA/NDFA starting at the initial state ends in an after reading the string.	NDFA
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
A symbol X is reachable _________________________.	if S →* aXβ
A transition function δ : Q × (Σ ∪ {ε}) → 2Q.	δ
A transition function: Q × (Σ∪{ε}) × S × Q × S*	δ
A transition function: Q × (Σ∪{ε}) × S × Q × S*.	δ
A' will contain how many elements from the original set A?	0
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
According to what concept is CFL a superset of RL?	Chomsky Hierarchy
All functions are relations	True
All relations are functions	False
All trees contain loops.	False
An algorithms to shampoo your hair.	rinse, lather, repeat
An alphabet is any finite set of symbols.	TRUE
An automaton that produces outputs based on current input and/or previous state is called.	Transducer
An English like abbreviations representing elementary computer operations.	Assembly Language
An example string w of a language L characterized by equal number of As and Bs is _______________.	ABBBAA
An indirect way of building a CFG is to _____________	build a PDA and then construct a CFG from it
An initial state q0 ∈ Q	q0
An initial state q0 ∈ Q.	q0
An order rooted tree that graphically represents the semantic information a string derived from a context-free grammar.	Derivation tree
An ε-NFA with a stack is also regarded as:	A PDA
Any production rule in the form A → B where A, B ∈ Non-terminal is called unit production.	TRUE
Any production rule in the form A → B where A, B ∈ Non-terminal is called.	Unit Production
Any set that represents the value of the Regular Expression is called a Property set.	FALSE
Are ambiguous grammar context free?	TRUE
are parameterized statement, they are true or false depending on the values of their parameters.	predicates
Blank symbol	Δ
challenged the mathematical community to find an infallible, mechanical method for constructing and checking truth of mathematical statements.	David Hilbert
Checking whether there is a matching parenthesis in a computer code can be done by a ______________.	context-free grammar
Circuits in graphs are always simple paths.	True
Computer science has roots in two fields :	Mathematics
Computers are general purpose because they can perform many different tasks.	TRUE
Connected graphs have components.	False
Context Free Languages is closed under intersection.	False
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
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
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
Elimination of productions and symbols is called simplification of CFGs. Simplification essentially comprises of the following steps:	Reduction of CFG
Empty set is a/an ________________.	Finite set
Empty string	Σ
Every context free grammar can be transformed into an equvalent non deterministic push down automata.	TRUE
Every set is a / an ________________ of itself.	Improper Subset
Finite Automata all regular languages and only regular languages.	Accept
Finite set of input alphabets	Σ
Finite set of input alphabets.	Σ
Finite set of states	Q
Finite set of states.	Q
For a regular expression 'a', we can construct the following FA:	TRUE
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 .
For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa	TRUE
For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.	TRUE
For every pair of regular expressions R and S, the languages denoted by R(SR)* and (RS)*R are the same.	TRUE
For the given Regular expression, the minimum number of terminals required to derive its grammar (011+1)*(01)* is	3,6,2,5,4
Given that the language L = {ε}, is L empty?	No, because the language has an empty symbol
Given the language L = {ε}, is L empty?	No, because the language has an empty symbol
Given the productions S → αXβ, X → a, ___________________.	X is useful
Global Positioning System (GPS) calculates latitude and longitude from satellite signals.	True
Having the initial state as a final state, give the deterministic finite state automaton that accepts the regular expression.	((a.b)+c)*
How many rational and irrational numbers are possible between 0 and 1?	Infinite
How many sets belong to the power set of A = {a,b,c,d}?	16
Identify the modeling recognition of the word "then"	Start State
If A →* ε, then we can say that:	A is nullable
If A = {0,2) and B = {1,3), then Cartesian product is?	A x B not equal B x A
If A = {3, 4, 6, 8} and	{ 4,6}
If A = {5,6,7} and B = {7,8,9} then A U B is equal to:	{5,6,7,8,9}
If A has m elements and B has n elements, then A x B has elements?	m x n
If a problem can be shown that it belongs to the class of recursively enumerable languages then ______________________.	It may be solved by any TM
If L is recursively enumerable then ________________.	L may not be recursively enumerable
If L1 and L2 are regular sets then intersection of these two will be	Regular
If L1 and L2 are regular sets then intersection of these two will be.	Regular
If R = {(1,1),(2,3),(4,5)}, then domain of the function is?	Dom R = {1,2,4}
If R ={(1,1),(2,3),(4,5)}, then the Range of the function is?	Range R = {1,3,5}
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
If Σ2 is {00, 01, 10, 11}, then Σ =	{0, 1}
In ____ Allan M. Turing proposed the Turing machine as a model of "any possible computation".	1936
In _____ Allan M. Turing proposed the Turing machine as a model of "any possible computation".	1936
In Allan M. Turing proposed the Turing machine as a model of "any possible computation".	1936
In mathematical notation, the symbol → means...	implication
In the Chomsky Hierarchy:	Regular Language ⊂ Context-sensitive Language
In words, H → C means…	Whenever H holds, C follows
Increasing accuracy, or precision	Minimizing False Positives
Increasing accuracy, or precision.	Minimizing False Positives
Increasing coverage, or recall.	Minimizing False Negatives
Is a finite set of states.	Q
Is a finite set of symbols called the alphabet.	Σ
Is a set of final state/states of Q (F ⊆ Q).	F
Is the initial state from where any input is processed (q0 ∈ Q).	q0
Is the transition function where δ: Q × Σ → Q.	δ
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
Is used to derive a string using the production rules of a grammar.	Production
It generate context-free languages. The productions must be in the form A → γ	Type-2 grammars
IT generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars.	Type-0 grammars
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
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.	Σ *
It process information in their efforts to eat, survive, and reproduce.	Living Organisms
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
It starts from the bottom with the string and comes to the start symbol using a parse tree.	Bottom-Up Parser
It starts from the top with the start-symbol and derives a string using a parse tree.	Top-Down Parser
JASON can generally be parsed by ______________.	A CFG
Labeled by a non-terminal symbol.	Vertex
Labeled by a terminal symbol or ε.	Leaves
Labeled by the start symbol.	Root Vertex
Language may be derived from other strings using the productions in a grammar.	FALSE
Leibniz introduced binary notation of calculation.	FALSE
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
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
NFA means:	Nondeterministic Finite Automaton
Noam Chomsky gave a mathematical model in ___ which is effective for writing computer languages.	1956
Noam Chomsky gave a mathematical model in _______ which is effective for writing computer languages.	1956
Noam Chomsky gave a mathematical model in which is effective for writing computer languages.	1956
Non-terminal symbols	S & A
NP-Hard problems are problems that are...	intractable
Number of final state require to accept in minimal finite automata.	None of the mentioned
Number of states require to accept string ends with 10.	3
One of the first programmable electronic computers in 1945.	ENIAC
Production Rule: aAb->agb belongs to which of the following category?	Context Sensitive Language
Recursive : TM that always halt = ________________ : TM that may or may not halt	recursively enumerable
Regular expression Φ* is equivalent to	ϵ
Regular expression Φ* is equivalent to.	ϵ
Regular sets are closed under union,concatenation and kleene closure.	TRUE
S → aAb, aA →aaAb, A→ε	P
Set of all tape symbols	Γ
Set of final or accepting states	F
Set of final or accepting states.	F
Some graphs contain cycles.	True
Start symbol, S ∈ N	S
Starting state	q0
T generate recursively enumerable languages. The productions have no restrictions and phase structure grammar including all formal grammars.	Type-0 grammars
Terminal symbols	a & b
The _____ of two sets A and B is the set containing those elements which are elements of A or elements of B.	union
The __________ of a Turing machine depends on the current state of finite control and the tape symbol present in the input tape.	single move
The algebraic law of regular expression described by E + E = E is _____________.	Idempotent
The algebraic law of regular expression described by φE = φ = Eφ is _______________.	Annihilator
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
The body of a production in CFG is composed of:	a string of terminals and non-terminals
The cardinality of the union of two disjoint sets is less than the sum of the cardinality of the given sets.	True
The CFG "S → (S) | SS | ε" accepts:	the string "((()))(())(())"
The commutativity property of set operations states that the union of any set with same set is the set itself.	False
The complement of an infinite language is necessarily finite.	FALSE
The difference between DFA and NFA	DFA can exist in only one state at a given time while NFA can exist in multiple states
The difference between regular expressions and finite automata is _____________.	that regular expressions are more program syntax-like while automata are more machine-like
The empty set is always a subset of any set.	True
The entity which generate Language is termed as regular languages.	FALSE
The entity which generate Language is termed as:	Grammar
The first counting machine developed 5000 years ago in the Middle East.	Abacus
The first mechanical calculator using gears for calculation developed in 1642.	Pascaline
The following are phases of C++ Programs except	Process
The initial stack top symbol (I ∈ S)	I
The initial stack top symbol (I ∈ S).	I
The initial state (q0 ∈ Q)	q0
The intersection of sets A and B is expressed as _________________.	A ∩ B
The language L contains all strings over the alphabet {a,b} that begin with and end with	a,b
The minimum number of states required to recognize an octal number divisible by 3 are/is.	3
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
The of a Turing machine depends on the current state of finite control and the tape symbol present in the input tape.	Single Move
The PDA has infinite memory and access in _____ order and the finite automata has ____ memory.	LIFO, finite
The power set of a given set does not contain the set itself.	False
The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.	TRUE
The relationship between recursive and recursively enumerable languages is ________________.	⊂
The stack content	s
The stack contents	s
The stack contents.	s
The start symbol.	S
The string "0000111" is accepted by _____________.	the CFG S → 0S1 | A, A → 0A | ε
The string aaaabbbccaaad is accepted by this regular expression	a*b*c*a*d*
The string abe is accepted by this regular expression.	a*b*c*a*d*e+
The string acde is accepted by this regular expression.	a*b*c*a*d*e+
The symbol used for the empty string is ____________.	ε
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
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
The top symbol is read and removed.	Pop
The transition a Push down automaton makes it additionally dependent upon the	Stack
The transition a Push down automaton makes it additionally dependent upon the _____.	stack
The unconsumed input	w
The unconsumed input.	w
The union of sets A and B is expressed as?	A U B
There are 5 tuples in finite state machine.	TRUE
Transition function	δ
Turing hypothesis believed that a function is said to be computable if and only if it can be computed by a Turing machine.	FALSE
Unconsumed input	w
Unconsumed input.	w
What are strings?	A string is a finite sequence of symbols chosen from Σ
What can be said about CFLs?	It is closed under •
What can be said about undecidable problems?	They are not recursive
What can not be said about CFLs?	It is closed under —
What cannot be said about automata theory?	None of the choices
What concept did Alan Turing introduce?	The concept of decidability
What is a grammar?	A device that enumerates the sentences of a language
What is a language?	A collection of finite-length sentences that were constructed from a finite set of symbols
What is a Universal TM?	a TM that stimulates another TM
What is an undecidable problem?	When a TM cannot make a decision on an instance of the problem
What is an ε-NFA?	It is an NFA with at least one explicit ε-transition defined
What is automata theory?	All of the choices
What is the final result after converting the following NFA-ε to NFA without Null move.	What is the final result after converting the following NFA-ε to NFA without Null move.
What kind of languages does a TM decide?	recursively enumerable
Which among the following cannot be accepted by a regular grammar?	L is a set of 0n1n
Which among the following is not a part of the Context free grammar tuple?	End Symbol Corre
Which among the following is the  option for the given grammar? G->X111|G1,X->X0|00.	{0a1b|a=2,b=3}
Which of the following is a not a part of 5-tuple finite automata?	Output Alphabet
Which of the following Set Operations produces the set that contains everything that is in Set A and in Set B?	Union
Which of the following statement is false in context of tree terminology?	Root with no children is called a leaf
Which of the following statements are  for a concept called inherent ambiguity in CFL?	Every CFG for L is ambiguous
Which of the following statements is true about NPDA, DPDA, and RL?	RL ⊂ DPDA ⊂ NPDA
Which of the following ways can be done to simplify a CFG?	Eliminate productions of the form A → B
Which of the following will not be accepted by the following DFA?	ababaabaa
Which one is the answer?	Computer
Who is the father of modern computer science?	Alan Turing
Who is the father of modern computer?	Charles Babbage
Z2 uses electricity to convey letters and transmit information quickly in 1844.	TRUE
__ is a finite set of states.	Q
__ is a finite set of symbols called the alphabet.	Σ
__ is a set of final state/states of Q (F ⊆ Q).	F
__ is the initial state from where any input is processed (q0 ∈ Q).	q0
__ is the transition function where δ: Q × Σ → Q.	δ
______ is used to derive a string using the production rules of a grammar.	Parsing
“C if H” is also the same as saying _______.	“If H then ”
“If H then ” is also the same as saying _______.	“C if H”
“Whenever H holds, C follows” can also be said as _______.	H → C
{Q, Σ, q0, F, δ, Q × Σ → Q} is…	There is no such tuple
Starts from tree leaves. It proceeds upward to the root which is the starting symbol S	bottom-up approach
Starts from tree leaves. It proceeds upward to the root which is the starting symbol S.	Bottom-Up Approach
Starts with the starting symbol S. It goes down to tree leaves using productions.	Top-Down Approach
|-* is the _____ closure of |-	transitive and reflexive
|-* is the closure of |-	Transitive and Reflexive
A _____ may or may not read an input symbol, but it has to read the top of the stack in every transition	PDA
A __________ of a derivation is a tree in which each internal node is labeled with a nonterminal.	parse tree
A - B will contain elements in?	A not in B
A ⊂ B is read as ________________.	A is a proper subset of B
A 2-Tape Turing Machine ___________________.	can show that recursive languages are closed under union
A compact textual representation of a set of strings representing a language.	Regular Expressions
A conceptual design for a machine consisting of a Mill, Store, Printer, and Readers.	Analytic Engine