NEW
Font size
WorksheetsMID2 assignment
Total questions: 25
Worksheet time: 13mins
Which of the following grammar is ambiguous
S−>aSb∣bSa∣SS∣ε
X→X+X∣X∗X∣X∣a
Both B and C
CFG can be recognized by a
PDA
FA
TM
A and C
A given grammar is called ambiguous if
two or more productions have the same non-terminal on the left hand side
a derivation tree has more than one associated sentence
there is a sentence with more than one derivation tree corresponding to it
brackets are not present in the grammar
How to eliminate ambiguity
precedence rules
using semantics
associativity rules
All the above
How to reduce CFG
By eliminating epsilon transitions
By eliminating unit productions
By removing useless symbols
All the above
S -> AB/a A -> BC/b B -> aB/C C -> aC/B .
Which one is useless symbol
A
B
C
A,B and C
S -> aSb/aAb/ab/a A -> ε. New productions after removing epsilon
S -> aSb/aAb/ab/a
S -> aSb/aAb/ab/a,S->aba
S -> aSb/aAb/ab/a, S->abb
S -> aSb/aAb/ab/a,S->aab
Which of the following is a unit production
A->b
A->B
B->b
C->a
Which of the following are normal forms?
Chomsky normal form
Grieback normal form
Both A and B
None
Rules for CNF:
Non-terminal->Non-terminal.Non-terminal
Non-terminal->terminal
Non-terminal->terminal.Non-terminal
Non-terminal->terminal
Non-terminal->Non-terminal.terminal
Non-terminal->terminal
Non-terminal->terminal,terminal
Non-terminal->terminal
Rules for GNF:
Non-terminal-> any no. of non-terminals
Non-terminal->terminal
Non-terminal-> one non terminal
Non-terminal->terminal
Non-terminal-> one Non terminal.(any no. of terminals)
Non-terminal->terminal
Non-terminal-> one terminal.(any no. of non-terminals)
Non-terminal->terminal
Which of the productions are in CNF
A->CD
A->a
A->BC
All the above
Which of the following productions are in GNF?
A->a
A->ab
A->aB
A and C
Which of the following is false?
The CFLs are not closed under klen closure
The CFLs are closed under concatenation
The CFLs are closed under klen closure
The CFLs are not closed under complement
How to represent PDA?
using 5 tuple
using 6 tuple
using 7 tuple
using 8 tuple
What is PDA?
NFA+stack
DFA+stack
NFA+tape
None
How to represent transition function in PDA
using a pair
using triplet
both
None
The language accepted by PDA?
Regular Language
Context free language
Both
None
The size of stack in PDA
5
infinte
10
None
Г indicates in PDA
set of states
set of input symbols
set of stack symbols
None
In how many ways acceptance is possible in PDA?
1
2
3
4
Which of the following is correct.
PDA can accept the strings using Acceptance by final state
PDA can accept the strings using Acceptance by empty stack
Both
None
Finite automata is superset of PDA
True
False
PDA can accept all the languages accepted by FA.
True
False
δ(q,a,X). What is X in this triplet>
input
Top of the stack
state
None
