Question # 1
The production of the form: nonterminal –> one nonterminal is called the __________ Select correct option:
Unit production
NULL production
Terminal production
Non Terminal production
Question # 2
A _________ is the one for which every input string has a unique path through the machine.
Deterministic PDA
nondeterministic PDA
PUSHDOWN store
Input Tape
Question # 3
In the null production N –> ^ , N is a
Terminal
Non terminal
Word
None of the given options
Question #5
The major problem in the earliest computers was
To store the contents in the registers
To display mathematical formulae
To load the contents from the registers
To calculate the mathematical formula
Question # 6
In polish notation, (o-o-o) is the abbreviation of………?
Operand – Operator – Operand
Operand – Operand- Operator
Operator -Operand – Operand
Operand -Operand – Operand
Question # 7
The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by the ………… production trees.
One
Two
More than one
At most one
Question # 8
The input string is placed, before it runs, in
Stack
Memory
Tape
Ram
Question # 9
Which of the following states is not part of PDA
START
ACCEPT
WRTITE
REJECT
Question #10
The production S –> SS | a | b | ^ can be expressed by RE
(a+b)+
(a+b)
(a+b)*
(ab)*
Question # 11
The locations into which we put the input letters on “Input Tap” are called __________
words
alphabets
cells
elements
Question # 12
“CFG” stands for _________
Context Free Graph
Context Free Grammer
Context Finite Graph
Context Finite Grammer
Question # 13
In a CFG the nonterminal that occurs first from the left in the working string, is said to be
Least Significant nonterminal
Most Significant nonterminal
Left most nonterminal
Left most derivate
Question # 14
The unit production is
Terminal –> Terminal
Terminal –> Non Terminal
Non terminal –> Terminal
Non terminal –> Non Terminal
Question # 15
A _____ operator adds a new letter at the top of STACK
PUSH
POP
READ
APPEND
Question # 16
PDA stands for ________
Push and Drop Automaton
Pop and Drop Automaton
Push Down Automaton
None of given options
Question # 17
The production of the form: Nonterminal-> ^ is said to be ______ production
NULL
UNIT
Chomsky form production
None of the given options
Question # 18
If a CFG has a null production, then it is ______
Posiible to construct another CFG without null production accepting the same language with the exception of the word
Not possible to construct another CFG without null production accepting the same language with the exception of the word
Called NULL CFG
Called Chmosky Normal Form (CNF)
Question # 19
If an FA has N state then it must accept the word of length
N-1
N+1
N
2N
Question # 20
In CFG, the symbols that cannot be replaced by anything are called
Terminals
Non terminals
Productions
None of the given options
Question # 21
For a non regular language there exist …… FA
One
At least one
At most one
No
Note: It is to be noted that a nonregular language, by Kleene’s theorem, can’t be accepted by any FA or TG.
Question # 22
Two languages are said to belong to same class if they end in the same state when they run over an FA, that state
Must be final state
May be final state or not
May be start state or not
None of the given option
Question # 23
The strings or words which do not belong to a language are called………of that language
Intersection
Union
Complement
Quotient
Question # 24
Set of all palindromes over {a,b}is regular
True
False
Question # 25
A non-regular language can be represented by
RE
FA
TG
None of the given options
The language that cannot be expressed by any regular expression is called a Nonregular language.
Question # 26
(a* + b*)* = (a + b)* this expression is __________
True
False
Question # 27
If S = { x }, then S* will be
{x,xx,xxx,xxxx,…}
{^ ,x,xx,xxx,xxxx,…}
Question # 28
The states in which there is no way to leave after entry are called
Davey John Lockers
Dead States
Waste Baskets
All of the given options
Question # 29
If S = {ab, bb}, then S* will not contain
Abbbab
Bbba
ababbb
bbbbab
Question # 30
According to theory of automata there are _________ types of languages
1
2
3
4
Question # 31
What do automata mean?
Something done manually
Something done automatically
Question #32
What is false about the term alphabet?
It is a finite set of symbols.
It is usually denoted by Greek letter sigma
It can be an empty set.
Strings are made up of its elements
Question # 33
Formal is also known as _________
Syntactic language
Semantic language
Informal language
Nsone of these
Question # 34
Introduction to languages
There are two types of languages
Formal Languages (Syntactic languages)
Informal Languages (Semantic languages)
Kleene star closure can be defined
Over any set of string
Over specific type of string
Question # 35
While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled by
A
B
null string
None of the given options