JNTU B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (March - 2021 - R13/R15)

Regular expression identities are algebraic laws used to manipulate and simplify expressions while maintaining language equivalence. The following are the fundamental identities:

• ε-Closure Identities: ε + R = R + ε = R, and Rε = εR = R.
• Annihilation: ∅R = R∅ = ∅ and ∅* = ε.
• Idempotence: R + R = R.
• Commutativity: R + S = S + R.
• Associativity: (R + S) + T = R + (S + T) and (RS)T = R(ST).
• Distributivity: R(S + T) = RS + RT and (S + T)R = SR + TR.
• Kleene Star Identities: R* = (ε + R)* = (ε + R)R* = R*R + ε, and (R*S)*R* = (R + S)*.
• Shifting Rule: (RS)*R = R(SR)*.

LEX is a computer program generator designed to create lexical analyzers (scanners). It takes a set of high-level descriptions of tokens as input and produces a C program that implements a finite automaton to recognize those tokens.

The LEX process involves three main sections:

• Definitions: Contains declarations of manifest constants, regular definitions, and start conditions.
• Rules: The core section containing patterns (regular expressions) and the corresponding actions (C code) to be executed when a pattern is matched.
• User Subroutines: Contains auxiliary C functions used by the actions in the rules section.

The input file, typically named lex.l, is processed by the LEX compiler to generate lex.yy.c. This file is then compiled by a standard C compiler to produce the executable lexical analyzer, which reads an input stream of characters and produces a stream of tokens for the parser.