Register

GO Classes DPP | COMPILER|LEXICAL ANALYZER

333 views
3 3 votes

Consider the following regular expression over the alphabet $\Sigma=\{a, b\}$ that represents a specific class of tokens in a new programming language:
$$
r=(a+b)^* a b b
$$
A lexical analyzer uses a Minimal Deterministic Finite Automaton (DFA) to recognize this pattern. If the DFA is constructed using the standard powerset construction from an NFA, how many states will the Minimal DFA contain?

2 Answers

0 0 votes
For a pattern of length $n$ representing "ends with [string]", the minimal DFA requires $n+$ 1 states. Here $n=3(a b b)$, so $3+1=4$ states.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | PYT...Next → · GO Classes DPP | COM...
← Previous in category · GO Classes CS Test S...Next in category → · GO Classes DPP | COM...
Position:
Show:

Related questions

0 0 votes
2 2 answers
284
284 views
GO Classes asked Jan 20
284 views
GO Classes DPP | COMPILER|LIVE VARIABLE ANALYSIS
Consider the following basic block consisting of three-address code instructions. Assume that only the variable $\verb|x|$ is "live" at the exit of this basic block.1. a ...
1 1 vote
1 1 answer
232
232 views
GO Classes asked Jan 20
232 views
GO Classes DPP | COMPILER|TAC
Consider the following C-style code segment:while (a < b) { if (c < d) x = y + z; else x = y - z; }Assume this code is translated into Three-Address Code (TAC) us...
1 1 vote
1 1 answer
268
268 views
GO Classes asked Jan 20
268 views
GO Classes DPP | COMPILER|DAG
In a compiler's optimization phase, a Directed Acyclic Graph (DAG) is constructed for the following basic block:1. t1 = a + b 2. t2 = c * d 3. t3 = t1 + t2 4. t4 = a + b ...
1 1 vote
1 1 answer
259
259 views
GO Classes asked Jan 20
259 views
GO Classes DPP | COMPILER|SDT
Consider the following S-attributed SDT scheme used to calculate the value of an expression. The grammar generates simple arithmetic additions and is suitable for an LR p...