All Exams >
Computer Science Engineering (CSE) >
Compiler Design >
All Questions
All questions of Lexical Analysis for Computer Science Engineering (CSE) Exam
Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.a) 2Nb) 2^Nc) N!d) none of theseCorrect answer is option 'B'. Can you explain this answer?
|
Arindam Goyal answered |
Solution:
The given question is related to the conversion of NFA to DFA and finding the maximum number of states in an equivalent minimized DFA.
NFA to DFA Conversion:
- To convert NFA to DFA, we need to follow the subset construction algorithm. In this algorithm, we consider each state of the DFA as a set of NFA states.
- Initially, the start state of the DFA is the epsilon closure of the start state of the NFA.
- Then, for each input symbol, we find the set of states reachable from the current state of DFA by that input symbol. This set becomes the next state of the DFA.
- We repeat this process for all the states of the DFA until we get all the possible states.
Minimization of DFA:
- After converting NFA to DFA, we need to minimize the DFA to get an equivalent DFA with the minimum number of states.
- We use the state minimization algorithm to minimize the DFA. In this algorithm, we merge the states of the DFA which are equivalent, i.e., they have the same set of outgoing transitions for all input symbols.
Maximum Number of States in Minimized DFA:
- The maximum number of states in an equivalent minimized DFA can be found using the Myhill-Nerode theorem.
- According to this theorem, the number of states in a minimized DFA is at least equal to the number of distinct equivalence classes of strings in the language of the NFA.
- The number of distinct equivalence classes of strings in the language of the NFA is equal to 2^N, where N is the number of states in the NFA.
- Therefore, the maximum number of states in an equivalent minimized DFA is 2^N.
Conclusion:
Hence, we can conclude that the maximum number of states in an equivalent minimized DFA is at least 2^N.
The given question is related to the conversion of NFA to DFA and finding the maximum number of states in an equivalent minimized DFA.
NFA to DFA Conversion:
- To convert NFA to DFA, we need to follow the subset construction algorithm. In this algorithm, we consider each state of the DFA as a set of NFA states.
- Initially, the start state of the DFA is the epsilon closure of the start state of the NFA.
- Then, for each input symbol, we find the set of states reachable from the current state of DFA by that input symbol. This set becomes the next state of the DFA.
- We repeat this process for all the states of the DFA until we get all the possible states.
Minimization of DFA:
- After converting NFA to DFA, we need to minimize the DFA to get an equivalent DFA with the minimum number of states.
- We use the state minimization algorithm to minimize the DFA. In this algorithm, we merge the states of the DFA which are equivalent, i.e., they have the same set of outgoing transitions for all input symbols.
Maximum Number of States in Minimized DFA:
- The maximum number of states in an equivalent minimized DFA can be found using the Myhill-Nerode theorem.
- According to this theorem, the number of states in a minimized DFA is at least equal to the number of distinct equivalence classes of strings in the language of the NFA.
- The number of distinct equivalence classes of strings in the language of the NFA is equal to 2^N, where N is the number of states in the NFA.
- Therefore, the maximum number of states in an equivalent minimized DFA is 2^N.
Conclusion:
Hence, we can conclude that the maximum number of states in an equivalent minimized DFA is at least 2^N.
Which of the following strings is not generated by the following grammar?S → SaSbS|ε- a)aabb
- b)abab
- c)aababb
- d)aaabbb
Correct answer is option 'D'. Can you explain this answer?
Which of the following strings is not generated by the following grammar?S → SaSbS|ε
a)
aabb
b)
abab
c)
aababb
d)
aaabbb
|
Siddharth Pillai answered |
Explanation:
S->aSbS putting S-> € and then S->SaSbS
S->aSaSaSbSbSbS putting S->SaSbS
S->aaabbb putting S->€.
S->aSbS putting S-> € and then S->SaSbS
S->aSaSaSbSbSbS putting S->SaSbS
S->aaabbb putting S->€.
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
- a)L = O
- b)L is regular but not O
- c)L is context free but not regular
- d)L is not context free
Correct answer is option 'B'. Can you explain this answer?
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
a)
L = O
b)
L is regular but not O
c)
L is context free but not regular
d)
L is not context free
|
Anjana Ahuja answered |
Unfortunately, I cannot answer this question without more information about the grammar S. Could you please provide the grammar rules or a description of the grammar?
The production Grammar is {S->aSbb,S->abb} is- a)Type-3 grammar
- b)Type-2 grammar
- c)Type-1 grammar
- d)Type-0 grammar
Correct answer is option 'B'. Can you explain this answer?
The production Grammar is {S->aSbb,S->abb} is
a)
Type-3 grammar
b)
Type-2 grammar
c)
Type-1 grammar
d)
Type-0 grammar
|
Abhijeet Mehta answered |
Explanation: As per the definition of type-2 grammar.
Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing “m” words, each of length ‘n’- a)m x 2n
- b)2mn
- c)2(m+n)
- d)All of the mentioned
Correct answer is option 'B'. Can you explain this answer?
Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing “m” words, each of length ‘n’
a)
m x 2n
b)
2mn
c)
2(m+n)
d)
All of the mentioned
|
Rajeev Menon answered |
For every Data here length is n and memory’s state is defined in terms of power of 2, Here the total memory capability for all the words = mn Hence the number of states is2^mn.
A programmer, by mistakes writes a program to multiply two numbers instead of dividing them, how can this error be detected- a)Compiler
- b)Interpreter
- c)Compiler or interpreter
- d)None of the mentioned
Correct answer is option 'D'. Can you explain this answer?
A programmer, by mistakes writes a program to multiply two numbers instead of dividing them, how can this error be detected
a)
Compiler
b)
Interpreter
c)
Compiler or interpreter
d)
None of the mentioned
|
Shraddha Iyer answered |
Explanation: This is a logical error can’t be detected by any compiler or interpreter.
Let L denotes the language generated by the grammar S ->OSO/00. Which of the following is true?
- a)L = O+
- b)L is regular but not O+
- c)L is context free but not regular
- d)L is not context free
Correct answer is option 'B'. Can you explain this answer?
Let L denotes the language generated by the grammar S ->OSO/00. Which of the following is true?
a)
L = O+
b)
L is regular but not O+
c)
L is context free but not regular
d)
L is not context free
|
|
Manasa Dey answered |
Explanation: The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.
Can you explain the answer of this question below:The lexical analyzer takes_________as input and produces a stream of_______as output.
- A:
Source program, tokens
- B:
Token, source program
- C:
Either of the two
- D:
None of the mentioned
The answer is a.
The lexical analyzer takes_________as input and produces a stream of_______as output.
Source program, tokens
Token, source program
Either of the two
None of the mentioned
|
Machine Experts answered |
Explanation: As per the definition of Lexical Analyser which states that lexical analysis is the process of converting a sequence of characters into tokens.
For operator precedence parsing, which one is true?- a)For all pair of non-terminal
- b)For all pair of terminals
- c)To delimit the handle
- d)None of the mentioned
Correct answer is option 'A'. Can you explain this answer?
For operator precedence parsing, which one is true?
a)
For all pair of non-terminal
b)
For all pair of terminals
c)
To delimit the handle
d)
None of the mentioned
|
Partho Joshi answered |
There are two important properties for these operator precedence parsers is that it does not appear on the right side of any production and no production has two adjacent non-terminals. Implying that no production right side is empty or has two adjacent non-terminals. So accordingly to property option (A) is correct.
If ∑ = {a, b, c, d, e, f} then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is- a)35
- b)360
- c)49
- d)720
Correct answer is option 'B'. Can you explain this answer?
If ∑ = {a, b, c, d, e, f} then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is
a)
35
b)
360
c)
49
d)
720
|
Nilesh Mukherjee answered |
Explanation: Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360.
Which of the following are Lexemes?- a)Identifiers
- b)Constants
- c)Keywords
- d)All of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following are Lexemes?
a)
Identifiers
b)
Constants
c)
Keywords
d)
All of the mentioned
|
|
Subhankar Shah answered |
Explanation: Different Lexical Classes or Tokens or Lexemes Identifiers, Constants, Keywords, Operators.
Which of the following pairs of regular expressions are equivalent?- a)1(01)* and (10)*1
- b)x (xx)* and (xx)*x
- c)x+ and x+ x(*+)
- d)All of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following pairs of regular expressions are equivalent?
a)
1(01)* and (10)*1
b)
x (xx)* and (xx)*x
c)
x+ and x+ x(*+)
d)
All of the mentioned
|
|
Bijoy Sharma answered |
Explanation:
Rule (pq)*p=p (qp)*
Therefore–(xx*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+
Rule (pq)*p=p (qp)*
Therefore–(xx*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+
Can you explain the answer of this question below:Which concept of grammar is used in the compiler
- A:
Lexical analysis
- B:
Parser
- C:
Code generation
- D:
Code optimization
The answer is b.
Which concept of grammar is used in the compiler
Lexical analysis
Parser
Code generation
Code optimization
|
Aditya Deshmukh answered |
As the lexical analysis of a grammar takes place in phases hence it is synonymous to parser.
Which of the following is not feature of compiler?- a)Scan the entire program first and translate into machine code
- b)To remove syntax errors
- c)Slow for debugging
- d)Execution time is more
Correct answer is option 'D'. Can you explain this answer?
Which of the following is not feature of compiler?
a)
Scan the entire program first and translate into machine code
b)
To remove syntax errors
c)
Slow for debugging
d)
Execution time is more
|
|
Abhijeet Mehta answered |
Explanation: The objective of the compiler is clearly not to increase the execution time of the program.
Which of the following is right?- a)A Context free language can be accepted by a deterministic PDA
- b)union of 2 CFLs is context free
- c)The intersection of two CFLs is context free
- d)The complement of CFLs is context free
Correct answer is option 'B'. Can you explain this answer?
Which of the following is right?
a)
A Context free language can be accepted by a deterministic PDA
b)
union of 2 CFLs is context free
c)
The intersection of two CFLs is context free
d)
The complement of CFLs is context free
|
Rohan Patel answered |
Explanation:
Context-free languages (CFLs) are a type of formal language that can be generated by a context-free grammar (CFG). A deterministic pushdown automaton (DPDA) is a type of automaton that can recognize a context-free language.
a) A Context-free language can be accepted by a deterministic PDA
This statement is true. A DPDA can recognize a context-free language by pushing and popping symbols onto a stack based on the rules of a CFG.
b) Union of 2 CFLs is context free
This statement is true. If we have two CFLs, we can construct a CFG that generates their union. We can do this by taking the union of the two CFGs and adding a new start symbol that derives the start symbols of the original CFGs.
c) The intersection of two CFLs is context free
This statement is false. The intersection of two CFLs may not be a CFL. There may be no CFG that generates the intersection of the two CFLs.
d) The complement of CFLs is context free
This statement is false. The complement of a CFL may not be a CFL. There may be no CFG that generates the complement of the CFL.
Therefore, the correct answer is option 'B'.
Context-free languages (CFLs) are a type of formal language that can be generated by a context-free grammar (CFG). A deterministic pushdown automaton (DPDA) is a type of automaton that can recognize a context-free language.
a) A Context-free language can be accepted by a deterministic PDA
This statement is true. A DPDA can recognize a context-free language by pushing and popping symbols onto a stack based on the rules of a CFG.
b) Union of 2 CFLs is context free
This statement is true. If we have two CFLs, we can construct a CFG that generates their union. We can do this by taking the union of the two CFGs and adding a new start symbol that derives the start symbols of the original CFGs.
c) The intersection of two CFLs is context free
This statement is false. The intersection of two CFLs may not be a CFL. There may be no CFG that generates the intersection of the two CFLs.
d) The complement of CFLs is context free
This statement is false. The complement of a CFL may not be a CFL. There may be no CFG that generates the complement of the CFL.
Therefore, the correct answer is option 'B'.
Regular expressions can be used only for values of type string and number.- a)True
- b)False
Correct answer is option 'A'. Can you explain this answer?
Regular expressions can be used only for values of type string and number.
a)
True
b)
False
|
|
Nishanth Roy answered |
Explanation: RE is used for all types of string and numbers.
Which one of the following statement is FALSE?
- a)Context-free languages are closed under union
- b)Context-free languages are closed under concatenation
- c)Context-free languages are closed under intersection
- d)Context-free languages are closed under Kleene closure
Correct answer is option 'C'. Can you explain this answer?
Which one of the following statement is FALSE?
a)
Context-free languages are closed under union
b)
Context-free languages are closed under concatenation
c)
Context-free languages are closed under intersection
d)
Context-free languages are closed under Kleene closure
|
Surbhi Kaur answered |
he FALSE statement is:
3. Context-free languages are closed under intersection.
Explanation:
- Context-free languages (CFLs) are closed under:
- Union: If L1L_1L1 and L2L_2L2 are CFLs, L1∪L2L_1 \cup L_2L1∪L2 is also a CFL.
- Concatenation: If L1L_1L1 and L2L_2L2 are CFLs, L1⋅L2L_1 \cdot L_2L1⋅L2 (concatenation) is also a CFL.
- Kleene closure: If LLL is a CFL, the Kleene closure (repetition) of LLL, denoted as L∗L^*L∗, is also a CFL.
However, CFLs are not closed under intersection. The intersection of two context-free languages is not necessarily a context-free language. In fact, the intersection of two CFLs may result in a language that is not context-free.
Which grammar defines Lexical Syntax- a)Regular Grammar
- b)Syntactic Grammar
- c)Context free Grammar
- d)Lexical Grammar
Correct answer is option 'D'. Can you explain this answer?
Which grammar defines Lexical Syntax
a)
Regular Grammar
b)
Syntactic Grammar
c)
Context free Grammar
d)
Lexical Grammar
|
|
Kunal Chaudhary answered |
The specification of a programming language often includes a set of rules, the lexical grammar, which defines the lexical syntax.
A compiler program written in a high level language is called- a)Source Program
- b)Object Program
- c)Machine Language Program
- d)None of the mentioned
Correct answer is option 'A'. Can you explain this answer?
A compiler program written in a high level language is called
a)
Source Program
b)
Object Program
c)
Machine Language Program
d)
None of the mentioned
|
|
Bijoy Sharma answered |
Explanation: The input that we give in high level language is also known as the source language.
Which concept of FSA is used in the compiler?- a)Lexical analysis
- b)Parser
- c)Code generation
- d)Code optimization
Correct answer is option 'A'. Can you explain this answer?
Which concept of FSA is used in the compiler?
a)
Lexical analysis
b)
Parser
c)
Code generation
d)
Code optimization
|
Pritam Chatterjee answered |
Explanation: Because the lexer performs its analysis by going from one stage to another.
Which of the following are not regular?- a)String of )’s which has length that is a perfect square
- b)Palindromes Consisting of 0’s 1’s
- c)String of 0’s whose length is a prime number
- d)All of the mentioned
Correct answer is option 'D'. Can you explain this answer?
Which of the following are not regular?
a)
String of )’s which has length that is a perfect square
b)
Palindromes Consisting of 0’s 1’s
c)
String of 0’s whose length is a prime number
d)
All of the mentioned
|
|
Amrutha Singh answered |
Explanation: Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.
The symbol table implementation is based on the property of locality of reference is- a)Linear list
- b)Search tree
- c)Hash Table
- d)Self Organisation
Correct answer is option 'C'. Can you explain this answer?
The symbol table implementation is based on the property of locality of reference is
a)
Linear list
b)
Search tree
c)
Hash Table
d)
Self Organisation
|
Tarun Saini answered |
Explanation: Hash table is used as a reference for symbol table because it is efficient.
Object program is a- a)Program written in machine language
- b)Program to be translated into machine language
- c)Translation of high-level language into machine language
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
Object program is a
a)
Program written in machine language
b)
Program to be translated into machine language
c)
Translation of high-level language into machine language
d)
None of the mentioned
|
|
Nishanth Roy answered |
Explanation: Since the input is the source language and the output that we get after the analysis is the machine language.
What constitutes the stages of the compilation process?- a)Feasibility study, system, design, and testing
- b)Implementation and. documentation
- c)Lexical analysis, syntax. Analysis and code generation
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
What constitutes the stages of the compilation process?
a)
Feasibility study, system, design, and testing
b)
Implementation and. documentation
c)
Lexical analysis, syntax. Analysis and code generation
d)
None of the mentioned
|
|
Ameya Goyal answered |
Explanation: As defined in the compilation process.
A system program that brings together separately compiled modules of a program into a form language that is suitable for execution- a)Assembler
- b)Linking loader
- c)Cross compiler
- d)None of the mentioned
Correct answer is option 'B'. Can you explain this answer?
A system program that brings together separately compiled modules of a program into a form language that is suitable for execution
a)
Assembler
b)
Linking loader
c)
Cross compiler
d)
None of the mentioned
|
|
Nishanth Roy answered |
Explanation: A loader which brings together the functions of a relocating loader with the ability to combine a number of program segments that have been independently compiled into an executable program.
An FSM with- a)M can be transformed to Numeral relabeling its states
- b)M can be transformed to N, merely relabeling its edges
- c)Both of the mentioned
- d)None of the mentioned
Correct answer is option 'C'. Can you explain this answer?
An FSM with
a)
M can be transformed to Numeral relabeling its states
b)
M can be transformed to N, merely relabeling its edges
c)
Both of the mentioned
d)
None of the mentioned
|
Rahul Chatterjee answered |
A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. ... An FSM is defined by a list of its states, its initial state, and the conditions for each transition.
What is the Regular Expression Matching Zero or More Specific Characters- a)x
- b)#
- c)*
- d)&
Correct answer is option 'C'. Can you explain this answer?
What is the Regular Expression Matching Zero or More Specific Characters
a)
x
b)
#
c)
*
d)
&
|
|
Amrutha Singh answered |
Explanation: Zero or Specific Expression matching can be done only by a single character that is*
The output of lexical analyzer is- a)A set of RE
- b)Syntax Tree
- c)Set of Tokens
- d)String Character
Correct answer is option 'C'. Can you explain this answer?
The output of lexical analyzer is
a)
A set of RE
b)
Syntax Tree
c)
Set of Tokens
d)
String Character
|
|
Sandeep Majumdar answered |
Explanation: A lexical analyzer coverts character sequences to set of tokens.
System program such a compiler are designed so that they are- a)Re-enterable
- b)Non-Usable
- c)Serially usable
- d)None of the mentioned
Correct answer is option 'A'. Can you explain this answer?
System program such a compiler are designed so that they are
a)
Re-enterable
b)
Non-Usable
c)
Serially usable
d)
None of the mentioned
|
|
Subhankar Shah answered |
Explanation: For the convince of the user compilers are made re-enterable.
All __________ are automatically treated as regular expressions.- a)Programmatic description
- b)Window
- c)Win Object
- d)Collection
Correct answer is option 'A'. Can you explain this answer?
All __________ are automatically treated as regular expressions.
a)
Programmatic description
b)
Window
c)
Win Object
d)
Collection
|
Arindam Malik answered |
Explanation: It is seen that programmatic description are treated as regular expression.
Chapter doubts & questions for Lexical Analysis - Compiler Design 2025 is part of Computer Science Engineering (CSE) exam preparation. The chapters have been prepared according to the Computer Science Engineering (CSE) exam syllabus. The Chapter doubts & questions, notes, tests & MCQs are made for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests here.
Chapter doubts & questions of Lexical Analysis - Compiler Design in English & Hindi are available as part of Computer Science Engineering (CSE) exam.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Compiler Design
26 videos|83 docs|30 tests
|
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up
within 7 days!
within 7 days!
Takes less than 10 seconds to signup