Font size
WorksheetsPushdown Automata Quiz
Total questions: 85
Worksheet time: 45mins
What is a pushdown automata?
A pushdown automata is a type of finite automaton that can use a queue to store and retrieve information during its operation.
A pushdown automata is a type of finite automaton that can only recognize regular languages.
A pushdown automata is a type of finite automaton that can only recognize context-free languages.
A pushdown automata is a type of finite automaton that can use a stack to store and retrieve information during its operation.
What is the main difference between pushdown automata and finite automata?
Pushdown automata have a tape, while finite automata do not.
Pushdown automata have a queue, while finite automata do not.
Pushdown automata have a memory, while finite automata do not.
Pushdown automata have a stack, while finite automata do not.
What is a deterministic pushdown automata?
A deterministic pushdown automata is an automaton that extends the capabilities of a non-deterministic finite automaton (NFA) by adding a stack.
A deterministic pushdown automata is an automaton that extends the capabilities of a Turing machine by adding a stack.
A deterministic pushdown automata is an automaton that extends the capabilities of a deterministic finite automaton (DFA) by adding a stack.
A deterministic pushdown automata is an automaton that extends the capabilities of a pushdown automata by adding a queue.
What is a non-deterministic pushdown automata?
A non-deterministic pushdown automata is a theoretical model of computation that can only accept regular languages.
A non-deterministic pushdown automata is a theoretical model of computation that does not use a stack.
A non-deterministic pushdown automata is a theoretical model of computation that extends the capabilities of a pushdown automaton by allowing multiple possible transitions for a given input symbol and stack symbol combination.
A non-deterministic pushdown automata is a theoretical model of computation that only allows one possible transition for a given input symbol and stack symbol combination.
What are the components of a pushdown automata?
Input alphabet, Stack alphabet, Set of states, Transition function, Initial state, Rejecting states
Input alphabet, Stack alphabet, Set of states, Transition function, Final state, Accepting states
Input alphabet, Stack alphabet, Set of states, Transition function, Start state, Accepting states
Input alphabet, Stack alphabet, Set of states, Transition function, Initial state, Accepting states
What is the purpose of a stack in a pushdown automata?
To store the input symbols.
To determine the final state of the automata.
To perform arithmetic calculations.
To keep track of the history of the computation.
Can a pushdown automata accept an infinite language?
Only if it has a finite number of states
Yes
Sometimes
No
What is the language accepted by a pushdown automata called?
regular language
Turing language
finite language
context-free language
What is the difference between a pushdown automata and a Turing machine?
A pushdown automata can only recognize context-free languages, while a Turing machine can recognize any recursively enumerable language.
A pushdown automata has a finite number of states, while a Turing machine has an infinite number of states.
A pushdown automata can only perform a limited number of operations, while a Turing machine can perform an infinite number of operations.
A pushdown automata has a limited memory capacity compared to a Turing machine.
What are the limitations of pushdown automata?
Inability to recognize certain context-free languages.
Inability to recognize deterministic context-free languages.
Inability to recognize non-context-free languages.
Inability to recognize regular languages.
What is the role of transitions in a pushdown automata?
What is the significance of the initial state in a pushdown automata?
The initial state determines the number of transitions in the pushdown automata.
The initial state has no significance in a pushdown automata.
The initial state determines the starting point and initial configuration of the pushdown automata.
The initial state determines the final configuration of the pushdown automata.
What is the significance of the final state in a pushdown automata?
The final state in a pushdown automata represents the initial state.
The final state in a pushdown automata has no significance.
The final state in a pushdown automata represents the number of transitions made.
The final state in a pushdown automata represents the acceptance or rejection of the input string.
What is the pumping lemma for context-free languages?
The pumping lemma for context-free languages is a property that states that for any context-free language L, there exists a constant p (the pumping length) such that any string s in L with length greater than or equal to p can be divided into three parts, s = uvw, satisfying the conditions mentioned above.
The pumping lemma for context-free languages is a property that states that for any context-free language L, there exists a constant p (the pumping length) such that any string s in L with length greater than or equal to p can be divided into five parts, s = uvwxy, satisfying the conditions mentioned above.
The pumping lemma for context-free languages is a property that states that for any context-free language L, there exists a constant p (the pumping length) such that any string s in L with length greater than or equal to p can be divided into four parts, s = uvwx, satisfying the conditions mentioned above.
The pumping lemma for context-free languages is a property that states that for any context-free language L, there exists a constant p (the pumping length) such that any string s in L with length greater than or equal to p can be divided into six parts, s = uvwxyz, satisfying the conditions mentioned above.
What is the difference between a deterministic pushdown automata and a non-deterministic pushdown automata?
The main difference between a deterministic pushdown automata and a non-deterministic pushdown automata is that the DPDA can only accept regular languages, while the NPDA can accept context-free languages.
The main difference between a deterministic pushdown automata and a non-deterministic pushdown automata is that the DPDA has at most one transition defined for each input symbol, while the NPDA can have multiple transitions defined for each input symbol.
The main difference between a deterministic pushdown automata and a non-deterministic pushdown automata is that the DPDA can have multiple transitions defined for each input symbol, while the NPDA has at most one transition defined for each input symbol.
The main difference between a deterministic pushdown automata and a non-deterministic pushdown automata is that the DPDA can only have a single stack, while the NPDA can have multiple stacks.
Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.
Turing Machine
Pumping Lemma
Arden’s theorem
None of the mentioned
While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into _________ parts.
2
5
3
6
If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
x
y
z
all of the mentioned
There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
n
|y|
|x|
none of the mentioned
Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L
i>0
i<0
i<=0
i>=0
If L1′ and L2′ are regular languages, then L1.L2 will be
regular
non regular
may be regular
none of the mentioned
If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
regular
non regular
may be regular
none of the mentioned
If A and B are regular languages, !(A’ U B’) is:
regular
non regular
may be regular
none of the mentioned
Suppose a language L1 has 2 states and L2 has 2 states. After using the cross product construction method, we have a machine M that accepts L1 ∩ L2. The total number of states in M:
6
4
2
8
Which among the following is the closure property of a regular language?
Emptiness
Universality
Membership
None of the mentioned
Inorder to simplify a context free grammar, we can skip the following operation:
Removal of null production
Removal of useless symbols
Removal of unit productions
None of the mentioned
In context to the process of removing useless symbols, which of the following is correct?
We remove the Nullable variables
We eliminate the unit productions
We eliminate products which yield no terminals
All of the mentioned
Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables that can produce strings only with the set of terminals.
{C}
{A,B}
{A,B,S}
None of the mentioned
Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
The variable which produces an epsilon is called:
a) empty variable
b) nullable
c) terminal
d) all of the mentioned
Which among the following is the format of unit production?
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned
Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb
Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No
The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?
a) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
Which of the following grammars are in Chomsky Normal Form:
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
Recursively enumerable languages are referred as
Type 0
Type 1
Type 2
Type 3
Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is
context-free ⊂ right-linear ⊂ context-sensitive
context-free ⊂ context-sensitive ⊂ right-linear
context-sensitive ⊂ right-inear ⊂context-free
right-linear ⊂context-free ⊂context-sensitive
Following context free grammar
S —> aB | bA
A —>b | aS | bAA
B —> b | bS | aBB
generates strings of terminals that have
equal number of a's and b's
odd number of a's and odd number b's
even number of a's and even number of b's
odd number of a's and even number of a's
Which of the following statement is correct?
All languages can not be generated by CFG
Any regular language has an equivalent CFG
Some non regular languages can't be generated by CFG
both (b) and (c)
The language accepted by a Push down Automata:
Type 0
Type 1
Type 2
Type 3
1. A CFG is ambiguous if
It has more than one rightmost derivations
It has more than one leftmost derivations
No parse tree can be generated for the CFG
None of the mentioned
A language that admits only ambiguous grammar:
Inherent Ambiguous language
Inherent Unambiguous language
Context free language
Context Sensitive language
9. Choose the correct option:
Statement: Unambiguity is the ideal structure of a language.
true
partially true
false
cant be said
In which order are the children of any node ordered?
From the left
From the right
Arbitrarily
None of the mentioned
Which among the following is the root of the parse tree?
Production P
Terminal T
Variable V
Starting Variable S
An NFA’s transition function returns
A Boolean value
A state
A set of states
An edge
Every grammar in Chomsky Normal Form is:
regular
context sensitive
context free
all of the mentioned
Every grammar in Chomsky Normal Form is:
regular
context sensitive
context free
all of the mentioned
If a and b be the regular expressions, then (a* ∪ b*) *
is equivalent to
(b* ∪ a*)*
(a ∪ b) *
(b ∪ a)*
All of above
The logic of pumping lemma is a good example of
pigeon-hole principle
divide-and-conquer technique
iteration
recursion
What is syntax in language theory?
The study of phonetics
Set of rules governing sentence structure
The meaning of words
A collection of words
What are the main components of a syntax tree?
trunk and bark
leaves and branches
nodes and edges
roots and stems
What is the difference between syntax and semantics?
Syntax is only applicable to programming languages, while semantics is applicable to natural languages as well.
Syntax and semantics are the same thing.
Syntax is about the meaning and interpretation, while semantics is about the structure and rules.
Syntax is about the structure and rules, while semantics is about the meaning and interpretation.
What is a context-free grammar?
A context-free grammar is a formal grammar that describes a formal language in terms of production rules that define how strings of symbols can be formed.
A context-free grammar is a data structure used in computer science.
A context-free grammar is a mathematical equation.
A context-free grammar is a type of programming language.
What are the four types of phrase structure rules?
Phrase Structure Rule for Noun (N), Phrase Structure Rule for Adjective (Adj), Phrase Structure Rule for Adverb (Adv), Phrase Structure Rule for Conjunction (Conj)
Phrase Structure Rule for Verb (V), Phrase Structure Rule for Adjective (Adj), Phrase Structure Rule for Adverb (Adv), Phrase Structure Rule for Conjunction (Conj)
Phrase Structure Rule for Sentence (S), Phrase Structure Rule for Noun Phrase (NP), Phrase Structure Rule for Verb Phrase (VP), Phrase Structure Rule for Prepositional Phrase (PP)
Phrase Structure Rule for Noun (N), Phrase Structure Rule for Verb (V), Phrase Structure Rule for Adverb (Adv), Phrase Structure Rule for Conjunction (Conj)
What is the Chomsky hierarchy?
The Chomsky hierarchy is a classification of mathematical theorems based on their complexity.
The Chomsky hierarchy is a classification of computer algorithms based on their efficiency.
The Chomsky hierarchy is a classification of formal grammars and languages into four levels based on their generative power.
The Chomsky hierarchy is a classification of programming languages based on their popularity.
What is the difference between a terminal and a non-terminal symbol?
A terminal symbol represents a non-terminal symbol, while a non-terminal symbol represents a terminal symbol.
A terminal symbol is used to terminate a program, while a non-terminal symbol is used to start a program.
A terminal symbol is used in the production rules, while a non-terminal symbol is used in the lexical rules.
A terminal symbol cannot be further expanded, while a non-terminal symbol can be expanded into other symbols.
What is the purpose of a parse tree?
To store the output of a program
To optimize the execution of a program
The purpose of a parse tree is to represent the syntactic structure of a sentence in a programming language.
To handle runtime errors in a program
What is the difference between leftmost and rightmost derivations?
The difference between leftmost and rightmost derivations is the number of non-terminals replaced.
The difference between leftmost and rightmost derivations is the order in which terminals are replaced.
The difference between leftmost and rightmost derivations is the number of terminals replaced.
The difference between leftmost and rightmost derivations is the order in which non-terminals are replaced.
What is ambiguity in syntax?
Confusing sentence structure
Lack of punctuation
Inconsistent word usage
Multiple possible meanings
What is the difference between a regular language and a context-free language?
A regular language can have nested structures, while a context-free language cannot have nested structures.
A regular language can be recognized by a Turing machine, while a context-free language can be recognized by a pushdown automaton.
A regular language can have an infinite number of strings, while a context-free language can have a finite number of strings.
A regular language can be recognized by a finite automaton, while a context-free language can be recognized by a pushdown automaton.
What is the pumping lemma for context-free languages?
The pumping lemma for context-free languages states that any context-free language L can be divided into six parts: uvwxyz, such that for any i ≥ 0, the string uv^iwx^iyz is also in L, where v and x are non-empty strings.
The pumping lemma for context-free languages states that any context-free language L can be divided into four parts: uvwxy, such that for any i ≥ 0, the string uv^iwx^iyz is also in L, where v and x are non-empty strings.
The pumping lemma for context-free languages states that any context-free language L can be divided into three parts: uvw, such that for any i ≥ 0, the string uv^iwx^iyz is also in L, where v and x are non-empty strings.
The pumping lemma for context-free languages is a property that states that any context-free language L can be divided into five parts: uvxyz, such that for any i ≥ 0, the string u(v^i)x(y^i)z is also in L, where v and y are non-empty strings.
What is the role of a pushdown automaton in syntax analysis?
A pushdown automaton is used to implement a parser in syntax analysis.
A pushdown automaton is used to optimize code generation in syntax analysis.
A pushdown automaton is used to perform semantic analysis in syntax analysis.
A pushdown automaton is used to generate lexical tokens in syntax analysis.
What is the difference between LL and LR parsing?
LL parsing is bottom-up, LR parsing is top-down.
LL parsing is more efficient than LR parsing.
LL parsing is used for parsing regular languages, LR parsing is used for parsing context-free languages.
LL parsing is top-down, LR parsing is bottom-up.
What is the purpose of a syntax-directed translation?
To convert source code into target code or representation.
To optimize the performance of the source code.
To generate documentation for the source code.
To debug and fix errors in the source code.
Design the regular expression for the language containing all the strings containing any no.of a’s and any no.of b’s.
ab
a*b*
(a+b)*
a*+b*
. Write regular expression for the language accepting the strings which are starting with 1 and ending with 0 over the set Σ={0,1}.
0(0+1)*1
0(0+1)*0
1(0+1)*1
1(0+1)*0
Write a Regular expression to denote a language L over Σ* where Σ={a,b} such that the 3rd character from right end of the string is always a
(a+b)*a(a+b)(a+b)*
(a+b)*a(a+b)(a+b)
(a+b)*a(a+b)*(a+b)*
(a+b)(a+b)a(a+b)
Ø+R=
Ø
R
Ɛ
None
ε+RR*=
ε
R
R*
None
According to Arden's Theorem if R=Q+RP then R=?
QP*
QP
RP
RP*
(0*1*)*=(0+1)*
True
False
(r+s)*= r*+s*
True
False
Whats the expression for q2
q2=1q1+1q2
q2=0q1+Ɛ
q2=0q2+(0+1)q3
None
According to unix syntax whats the meaning of [1,2,3,4]
1*2*3*4
1+2+3+4
1234
None
How to represent Regular grammar
(V,T,S,P)
(V,T,P,S)
(T,V,P,S)
(V,S,T,P)
Productions for q0
q0->aq0, q0->bq1
q0->aq0
q0->aq0, q0->bq1, q0->b
none
The following grammar is
S->Bb
B->Cb
B->Ba
C->a
B->b
Right Linear grammar
Left Linear Grammar
None
According to pumping lemma what is n?
n>=|z|
n<=|z|
any random value
None
Which of the following is not an application of pumping lemma
Power stations
Digital circuits
To prove language as non regular
Chess games
