Compiler Design
Assignment- Week 3
TYPE OF QUESTION:MCQ
Number ofquestions:10 Total mark: 10 X 1 = 10
Q1.
Ans: d)
Detailed Solution: Lex: A lexical analyzer generator that was one of the first tools used to
create scanners in Unix environments.
1. Flex: An enhanced and faster version of Lex.
2. JFlex: A lexical analyzer generator specifically designed for Java-based projects.
All of these tools are used for lexical analysis, which involves breaking input text into
tokens as part of the compilation process.
Q2.
Ans: d)
Detailed Solution: In a Lex specification file, "?" is not a valid operator. Common operators
in Lex include:
• *: Matches 0 or more occurrences of the preceding regular expression.
• +: Matches 1 or more occurrences of the preceding regular expression.
• ?: This is not a valid Lex operator and is typically associated with other regular
expression engines (e.g., in some contexts, it means 0 or 1 occurrence).
Q3.
Ans: a)
Detailed Solution:
A DFA can potentially have more states than an NFA. When converting an NFA to a DFA
(using the subset construction algorithm), the number of states in the DFA can be
exponentially larger in the worst case. For example, an NFA with n states could result in a
DFA with up to 2^n states.
Q4.
Ans: d)
Deatiled Solution:
Q5.
Ans: d)
Deatiled Solution:
A Lex specification file is divided into three sections, separated by %%:
1. Definition Section: Contains definitions for macros and declarations of variables.
2. Rules Section: Specifies patterns and corresponding actions.
3. User Code Section: Optional section containing additional C code to be included.
Each section is demarcated by %%. For example:
Definition Section
%%
Rules Section
%%
User Code Section
Q6.
Ans: a)
Detailed Solution:
ε-closure (epsilon-closure) of a state in an NFA is the set of all states that can be
reached starting from that state using only ε (epsilon) transitions, including the state
itself.
• An ε transition is a transition that consumes no input.
• The ε-closure of a state is computed by recursively exploring all states that can be
reached through ε transitions from the given state.
Q7.
Answer: d)
Deatiled Solution: Let’s analyze each option regarding the ε-closure of a subset S of states
Q:
1. a) Every element of S:
This is true because the ε-closure of S includes every element of S itself.
2. b) For any q∈ε-closure, every element of δ(q,ε)\ is in ε-closure:
This is true because the ε-closure of a state includes all states reachable by ε-
transitions.
3. c) No other element is in ε(S):
This is true because the ε-closure of S is precisely defined as the set of all states
reachable by ε-transitions, and no other states are included.
Q8.
Ans: b)
Detailed Solution: When a Lex program is processed, the Lex tool generates a C source
code file containing the lexical analyzer. By default, this file is named lex.yy.c.
• This file includes the code for the scanner based on the rules defined in the Lex
specification file.
• a) Lex.c: Not a default output of Lex.
• b) Lex.yy.c: The correct output file generated by Lex.
• c) Lex.l: The input specification file for Lex (not the output).
• d) Lex.yy.l: Not a valid file name in the Lex context.
Q9.
Ans: b)
Detailed Solution: Regular languages can be represented using multiple equivalent
formalisms. Let’s examine the options:
1. i) DFA:
DFAs can represent all regular languages, but there may be regular languages that
are easier to describe using NFAs or regular expressions.
2. ii) NFA:
NFAs can represent all regular languages. They are equivalent to DFAs in expressive
power but are often more concise.
3. iii) Regular Expressions:
Regular expressions can describe all regular languages. They provide a more
compact and human-readable way to define patterns.
Q 10.
Ans: c)
Detailed Solution:
A Lex program is divided into three sections, separated by %%:
1. Definition Section:
This section contains declarations, macros, and regular definitions. These are used
to define constants, patterns, or reusable components.
2. Rules Section:
Contains the core of the Lex program, where regular expressions are associated
with actions (C code) to execute when the patterns are matched.
3. User Code Section:
An optional section that includes any additional C code or functions that support the
Lex program.
Definitions Section
%%
Rules Section
%%
User Code Section
