GATE CSE 1990 | Question: 2-ix

Question

Match the pairs in the following questions:$$\begin{array}{ll|ll} (a) & \text{Lexical analysis} & (p) & \text{DAG's} \\\hline  (b) & \text{Code optimization} & (q) & \text{Syntax trees} \\\hline   (c) & \text{Code generation} & (r)  & \text{Push down automaton} \\\hline (d) & \text{Abelian groups} & (s)  & \text{Finite automaton}  \\ \end{array}$$

Comments

i dont get this question   i know only  lexical analysis ->  is done by F.A  , syntax tree /parse tree -> done by pda

code optimization--> by DAG     , code generation also done threw parse tree --> so pda

---

(a) LEXICAL  ANALYSER – (S) FINITE AUTOMATA

IN Lexical Analysis , finite automata are used to produce tokens or strings in the form of identifiers , keywords , constants from the program that will be stored in the symbol table and the lexical analyser plays a major role in their pattern recognition , as it identifies and provide token no. to the keywords in the symbol table .

(b) Code optimization – (P) DAG

at the syntax analyser, after generating the grammer  in the form of syntax tree / derivation tree from the given token string and then at semantic analyser , it will create the modified parse tree with modified parse tree as input , intermediate code will be generated . That intermediate is optimized making it consume fewer resources (i.e. CPU , MEMORY ) so that faster running m/c code will result.(optimized intermediate code). DAG(DIRECTED ACYCLIC GRAPH ) gives a tree like view to identify the common strings and eliminate them thus saving up some memory and making it faster to run .

© Code generation – (Q) Syntax tree

Semantic analyser which created the modified parse tree using the grammer / tree , we generate an intermediate code which is m/c independent code which we can run on any system.

(D) Abelian Groups – (R) Push Down Automata

Abelian group consist of all those sets which should satisfy :-

Algebraic structure - which satisfy closure property

Semigroup - Associative property (a + b) + c = a + (b + c)

Monoid - Identity element property (a + e = a)

Group - inverse property with identity element as output ( a + b = b + a = e )

where a = b^-1 , b = a^-1

Abelian Group - It should satisfy the commutative property

(a + b) = (b + a)

Answer 1

$$\small \begin{array}{ll|ll} (a) & \text{Lexical analysis} & (s) & \text{Finite automaton (DFA creation for finding tokens)} \\\hline  (b) & \text{Code optimization} & (p) & \text{DAG's (Common subtree minimization)} \\\hline   (c) & \text{Code generation} & (q)  & \text{Syntax trees (one can construct a derivation and }\\&&& \text{from it a parse tree that can be
used for code generation)}  \\\hline (d) & \text{Abelian groups} & (r)  & \text{ Push down automaton}   \end{array}$$

Comments

To check the word of the form $x^my^nx^{-j}y^{-k}$ is equal to the identity or not, we first use commutative property (as it is abelian group) this becomes = $y^nx^mx^{-j}y^{-k}$, now using PDA  we check if $j=m$ and $k=n$.

---

@Sachin what do you mean by "x^-j y^-k" ? negative powers in string?

---

negative powers means inverses
let inverse of $a$ is $b$
and inverse of $c$ is $d$.
$a^{-1} = b \\ c^{-1} = d \\$
then $aca^{-1}c^{-1}= acbd = abcd=e$ (here $\color{blue}e$ is identity element)

---

@Sachin inverse w.r.t. which operation? because if we take concatenation operation, then inverse doesn't exist.

---

Ok, I got my mistake. Thank you :)

---

ohk bro :)

---

Hello, Can anyone please explain the relationship between the abelian group and pda?

or please mention the reference document. Thanks

---

https://eiche.theoinf.tu-ilmenau.de/kuske/LOGINF/abstractStruengmann.pdf

---

Nice stuff.

---

Someone please explain me the relation between Abelian Groups and Pushdown Automata.

Edit: Got it from @Sachin Mittal 1 Sir's comment here: https://gateoverflow.in/84033/gate-cse-1990-question-2-ix?show=102932#c102932

---

@Deepak Poonia Sir, how do we relate Abelian Group with PDA . Is this relevant for GATE point of view

Answer 2

lexical analysis related to regular expression ( finite auotomata)

code optimization related to DAGs

as i know code generation is done on parse tree ( syntax tree + semantic meaning )

hence

A : S

B : P

C: Q

D : R ( dont sure about this option )

Answer 3

  a) lexical analysis   is related to     Syntax trees

lexical analysis generates tokens Tokens are frequently defined by regular expressions, which are understood by a lexical analyzer generator such as lex. ..and  regular expressions,are used in  Syntax analysis for genearating..syntax tree.

b)code optimization    is related to      p)DAG's

http://web.cecs.pdx.edu/~harry/compilers/slides/Optimize2.pdf

c)code generation   is related to   Push down automata

from the run of the push-down automaton, one can construct a derivation and from it a parse tree that can be used for code generation

d)abelian group          is related to        s)Finite automata

http://eiche.theoinf.tu-ilmenau.de/kuske/LOGINF/abstractStruengmann.pdf

Comments

1. i can't understand term related to.

2.if Lexical analyzer related to systax tree then why it is not related to PDA ?PDA used to parse syntax tree.

3. why lexical analyser not related to Finite Automata ? actually Lexical analysis done by FA only.

---

1)matching. 2)u r correct but ////sir...the question is of matching...pda & syntax tree are in same group...u can't do....it..what and i did it is also...not wrong.... 3)lexical analysis done by finite automata true...but...abelian groups can't be done by syntax tree..and the reason i provided is also true for lexical

---

but here no option matching like thing so u should need to write every possible solution.

---

thanky you sir...i will follow ur instructions & will update it soon...