Automata Theory Part D
Explore Automata Theory: Challenge Your Knowledge!
Welcome to the Automata Theory quiz, a comprehensive test designed to examine your understanding of various aspects of formal languages, grammars, and their corresponding automata. Gain insights into the complexities of automata theory while testing your knowledge with 37 engaging questions!
- Multiple choice format
- Covers topics like regular expressions and context-free grammars
- Perfect for students, educators, and enthusiasts
Which type of language is defined by regular expressions?
Type 0
Regular
Context-free
Type 1
What is the corresponding accepting machine for a context-free language?
Finite automaton
Turing machine
Deterministic pushdown automaton
Transition graph
What is the corresponding accepting machine for a Type 1 language?
Finite automaton
Deterministic pushdown automaton
Turing machine
Transition graph
Context-free grammar (CFG) is a ......
5-tuple
3-tuple
4-tuple
6-tuple
What is the purpose of a context-free grammar (CFG) in language processing?
To categorize statements of a language
To parse statements of a language
To optimize statements of a language
To compile statements of a language
CFG for a+
S→ aS | a | ^
S→ aS | a
S→ aS | b
None of these
For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
Non regular language
None of the mentioned
0❿1❿ | n>=1
0❿1❿ | n>=0
The context free grammar: X → XX | aXb | bXa | ɛ generates……
Number of a’s followed by any number of b’s
Equal number of a’s and b’s
None of these
Unequal number of a’s and b’s
The following production rules of a regular grammar generate a language L:S→ aS | bS | a |b The regular expression of L is
A + b
(a + b)*
(a + b)(a + b)*
(aa + bb) a*b*
What is the language generated by the following CFG: S → aSb | ε
The set of all strings of the form a❿b❿, where n is a non-negative integer
The set of all strings of the form a❿b❿c❿, where n is a non-negative integer
The set of all strings of the form a❿b❿c❿d❿, where n is a nonnegative integer
None of the mentioned
What is the language generated by the following CFG: S → aSb | bSa | ε
The set of all strings of the form a❿b❿, where n is a non-negative integer
) The set of all strings of the form a❿b❿c❿,where n is a non-negative integer
The set of all strings of the form a❿b❿c❿d❿, where n is a nonnegative integer
A subset of the set of all strings of the form a❿b❿, where n is a nonnegative integer
Which of the following is a valid production rule in a CFG?
S → aSb | bSa
S → a | b
S → ε
All of the above
Regular grammar is:
Context free grammar
English grammar
Non context free grammar
None of the mentioned
Which of the following statement is false?
Context free language is the subset of context sensitive language
Regular language is the subset of context sensitive language
Recursively enumerable language is the super set of regular language
Context sensitive language is a subset of context free language
The context free grammar S → SS | 0S1 | 1S0 | ɛ generates:
Equal number of 0’s and 1’s
Unequal number of 0’s and 1’s
Any number of 0’s followed by any number of 1’s
None of these
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
Even number of a's and even number of b's
Odd number of a's and odd number b's
Odd number of a's and even number of a's
Which of the following statement is correct?:
All Regular grammar are context free but not vice versa
Regular grammar and context free grammar are the same entity is the super set of regular language
All context free grammar are regular grammar but not vice versa
None of the mentioned
For L= {w: w starts and ends with the same symbol} the CFG is:
S → 0S0|1S1
S → 0S0|1S1|1|0
Both b and c
S → 0S0|1S1| ˄
For L= {w: |w| is odd} the CFG is:
S → 0S00|1S11 S → 0|1
S → 0S0|1S1 S →0|1
S → 0S00|1S11 S → 00|11
S → 0Y00|1Y11 Y →0|1
For L= {w: w=TTR is a palindrome with odd or even count of letters} the CFG is:
S → 0S0| S → ˄
S → 0S0|1S1 S → 0|1|˄
S → 0Y00|1Y11 Y →0|1
S → 0S0|1S1 S → 0|1
The most suitable data structure used to represent the derivations
Queue
Tree
Linked List
Hash Tables
For L= {a 𝑖 𝑝 2𝑖 ; count of a is twice count of b} the CFG is:
S → aSbb S → ˄
S → aSbb S → a|b
Both a and b
S → aSb S →aab
The Grammar can be defined as: C =(V, Σ, R, S) In the given definition, what does V represents?
A special start symbol.
Symbols called terminals of the alphabet
A finite set of variables
None
The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
3
5
7
2
Which of the following statement is correct?
All context free grammar are regular grammar but not vice versa
All Regular grammar are context free but not vice versa
None of the above
Regular grammar and context free grammar are the same entity
Which of the following language cannot be accepted by a regular expression?
Language of a set of 0n1n
Language of a set of binary complement
Language of a set of numbers divisible by 4
Language of a set of string with odd number of 0
Which of the following is sufficient to convert an arbitrary context free grammar (CFG) to an LL(1) grammar?
Ambiguity
left factoring
Left recursion
None of the above
Is a notation for defining context free languages :
Revision requirements
Variables
context-free grammar
Programming languages
Which of the following is not component of context free grammer…….. :
Terminal Symbols
Non-terminal Symbol
production rules
Regular exepression
Which of the following is property of all context free language…...:
They can be recognized by a finite automaton
They are closed under union and concatenation
They can be generated by a regular grammar
They are always infinite.
Which of the following is true about the pumping lemma for context-free languages:........
It applies only to regular languages
It can be used to prove that a language is context-free.
It states that all context-free languages are infinite
It guarantees that a context-free language is regular
Which of the following is an example of a context-free language………
{a^n b^n : n ≥ 0}
{0^n 1^m 0^(n+m) : n,m ≥ 0}
{w : w is a palindrome}
{a^n b^m c^k : n,m,k ≥ 0 and n=m or m=k}
Which of the following is NOT a property of context free grammar:
They can generate any recursively enumerable language
They can be used to describe the syntax of programming languages
) They can be used to describe the structure of sentences in natural languages.
They can be used to describe the structure of Computer Programs.
Which of the following is NOT a type of context-free grammar:
Unrestricted Grammars
Left-Linear grammars.
Right-Linear grammars
Context-sensitive grammars.
The Language of all …….. is NOT context-free
Strings of balanced parentheses.
Strings of balanced braces
Strings of balanced brackets.
All of the above.
Which of the following is NOT a way to decide whether a given string is in the language generated by a context-free grammar? :
Use a pushdown automaton.
Use a non-deterministic algorithm
Use a Turing machine.
Use a recursive algorithm.
Which of the following is NOT a way to generate the strings in the language generated by a context-free grammar?
Use a pushdown automaton
Use a Turing machine
Use a non-deterministic algorithm
Use a recursive algorithm.
{"name":"Automata Theory Part D", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Welcome to the Automata Theory quiz, a comprehensive test designed to examine your understanding of various aspects of formal languages, grammars, and their corresponding automata. Gain insights into the complexities of automata theory while testing your knowledge with 37 engaging questions!Multiple choice formatCovers topics like regular expressions and context-free grammarsPerfect for students, educators, and enthusiasts","img":"https:/images/course1.png"}
More Quizzes
Automata Theory True / False
301568
Automata Theory Part C
12669
Automata Theory Part A
50250
Automata Theory Part E
281466
Algorithms & Probability
1470
DS
1050
Dsa
15823
5.Asymptotic Notations and Basic Efficiency Classes
4261
Cs 505
70350
DEADLOCK
15810
6. MATHEMATICAL ANALYSIS FOR NON-RECURSIVE AND RECURSIVE ALGORITHMS
5258
Binary Tree and Operations
1586