**Complier Design Question and Answers**

*( Suggestion : keep refreshing the page for updated content* & Search Questions Using Find )

**Q1. Analyze the following line of code and show how the line is converted to target code in assembly language over the various phase of compiler a = bc*cd+50.00**

**b. Construct DFA for the language L(M) = {x | x is a string of (zero or more) ) a’s, b’s and c’s such that x does not contain the substring aa}**

To construct a deterministic finite automaton (DFA) for the language $L(M)={x∣x$ is a string of zero or more $a$‘s, $b$‘s, and $c$‘s such that $x$ does not contain the substring $aa$), we can follow these steps:Let’s define the DFA $M$ as follows:1. Set of States (Q):

Q={90, 91, 92}

qo is the initial state.

q₁ is the state after reading a single a

q₂ is an accepting state indicating that the string does not contain the substring aa.2. Input Alphabet (Σ):

E = {a,b,c}3. Transition Function (d):

δ(qo, a) = 91 (Reading a transitions to q₁)

d(qo, b) = qo (Reading b stays in qo)

* δ(40, c) = 40 (Reading c stays in go)

d(qı, a) = 92 (Reading a again leads to q2, which is an accepting state)

d(qı, b) = go (Reading b goes back to go)

8(41, c) = 40 (Reading c goes back to go)

• δ(92, a) = 42 (Once in q2, stay in q₂)

8(q2, b) = 92 (Once in q₂, stay in q₂)

8(92, c) = 42 (Once in q₂, stay in q₂)4. Start State (go):

qo is the start state.

5. Accepting State (q₂):

q2 is an accepting stateThe DFA $M$ is then defined as $M=(Q,Σ,δ,q_{0},{q_{2}})$.This DFA recognizes strings over the alphabet ${a,b,c}$ such that the substring $aa$ is not present in the string. It accepts strings that may contain any number of $a$‘s, $b$‘s, and $c$‘s, as long as there are no consecutive $a$‘s.

**Q2. Design regular expression for the following Languages:**

**a. L= {we {a, b}*w is even}.**

**b. L = {we {0, 1}*length of w is odd }.**

**c. L= {we {0, 1}*atmost one pair consecutive 1’s).**

**d. L= {w € {0, 1}*:**

**e. L = {we {a,b}*: the third character is 0) w contains an odd number of a’s}.**

**f. L = {we {0, 1}*: every pair of adjacent 0’s appears before any pair of adjacent 1’s}**

Let’s design regular expressions for the given languages:

a. $L={w∈{a,b_{∗}∣length ofwis even}$^(a{2}|b{2})*(a|b)?$

b. $L={w∈{0,1_{∗}∣length ofwis odd}$^(0|1)(0{2}|1{2})*(0|1)$

c. $L={w∈{0,1_{∗}∣at most one pair of consecutive 1’s}$`^(0*10*1{0,1}0*)*$`

d. $L={w∈{0,1_{∗}∣every block of 0’s is immediately followed by a block of 1’s}$`^((0+1+)+0*)*$`

e. $L={w∈{a,b_{∗}∣the third character is 0 andwcontains an odd number of a’s}$`^(.{2}0.*(a.*a){2})*a.*$`

f. $L={w∈{0,1_{∗}∣every pair of adjacent 0’s appears before any pair of adjacent 1’s}$`^(0*10*1*)*0*$`

These regular expressions are designed based on the given language descriptions. Keep in mind that there might be alternative solutions or variations depending on the specific interpretation of the language requirements.

**Q3. Consider the grammar**

**S→S && S**

**S→S || S**

**S→!S**

**S→ (S)**

**S→ true**

**S→ false**

**Write the parse tree, LMD and RMD for the expression true && true || false**

Sure, let’s build the parse tree, leftmost derivation (LMD), and rightmost derivation (RMD) for the expression

`true && true || false`

based on the given grammar:Grammar:
S → S && S S → S || S S → !S S → (S) S → true S → false

Expression: `true && true || false`

Parse Tree:

|| / \ && false / \ true true

S => S && S => true && S => true && S || S => true && true || S => true && true || false

S => S && S => S && true => S || true => true || true => true || false