JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II Year FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (April/May - 2023 - R16)

Kleene Closure of a language L, denoted by L*, is the set of all strings formed by concatenating zero or more strings from L. It is defined as L* = ∪_i≥0 Lⁱ, where L⁰ = {ε}.

Positive Closure of a language L, denoted by L⁺, is the set of all strings formed by concatenating one or more strings from L. It is defined as L⁺ = ∪_i≥1 Lⁱ, which is equivalent to L* - {ε}.

Finite Automata (FA) are fundamental models in computer science used for recognizing regular languages and designing systems with finite states. Key applications include:

• Lexical Analysis: Compilers use FA to scan source code and identify tokens such as keywords, identifiers, and operators by matching patterns defined by regular expressions.
• Text Processing and Pattern Matching: Algorithms like KMP or grep utilities use finite automata to efficiently search for specific patterns or strings within large datasets or documents.
• Protocol Verification: FA are used to model and verify communication protocols and hardware circuits to ensure they transition correctly between states and avoid deadlock or undefined behavior.
• Natural Language Processing: They are applied in morphological analysis, such as identifying the roots of words or checking spelling by verifying if word structures conform to predefined rules.