Lexical Analysis Questions and Answers

Q: Consider the following closure properties of regular languages.1. closed under union2. closed under concatenation3. closed under complementation

Correct answer: All of themRegular languages are closed under all three, and under intersection and difference besides. Union and concatenation follow directly from the regular expression operators; complementation follows from swapping accepting and non-accepting states of a complete DFA; and intersection then follows from the other two by De Morgan, or directly from the product construction.

Q: A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}.\(T_{1}:\ a?\,(b|c)^{*}a\)\(T_{2}:\ b?\,(a|c)^{*}b\)\(T_{3}:\ c?\,(b|a)^{*}c\)Note that 'x?' means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.If the string \(bbaacabc\) is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

The analyzer outputs \(T_{3}T_{3}\).It always takes the longest prefix any pattern matches. On bbaacabc:\(T_{1}\) can match bba (no leading a, then bb, then a): 3 characters.\(T_{2}\) can match only bb, since \((a|c)^{*}\) cannot absorb the second b: 2 characters.\(T_{3}\) can match bbaac (no leading c, then bbaa from \((b|a)^{*}\), then c): 5 characters.So the first token is \(T_{3}\), for bbaac. The rest is abc: \(T_{3}\) matches all of it (ab, then c), while \(T_{1}\) matches only a and \(T_{2}\) only ab. So the second token is \(T_{3}\) too.The options starting with \(T_{1}\) or \(T_{2}\) take a shorter prefix than the longest-match rule allows.

81.

Recognising the end of the input is signalled to the parser by

A.a distinguished end of file token returned by the scanner
B.the scanner returning no value at all from its next call
C.the parser detecting that no production can be applied
D.an exception raised by the input buffering routines

Answer: A

Correct answer: a distinguished end of file token returned by the scanner

The parser needs to know that the input has ended in the same form as everything else it consumes, so the scanner returns a special end of file token, conventionally written as a dollar sign in grammars. The grammar then has a production that accepts the start symbol followed by that token, which is how it recognises a complete program.

Discuss in Forum

82.

Two regular expressions are equivalent when

A.they can be written using the same character classes
B.they describe exactly the same set of strings
C.they contain the same number of operators and symbols
D.their nondeterministic automata have the same number of states

Answer: B

Equivalence is about the language denoted, not the notation. Minimising the deterministic automata of both and comparing them decides equivalence, since the minimal machine is canonical. Two expressions that look nothing alike may well denote exactly the same language.

Discuss in Forum

83.

The expression (a|b)* and the expression (a*b*)* denote

A.different languages, the first omitting the empty string
B.languages that cannot be compared by any known method
C.the same language, namely all strings over a and b
D.different languages, the second omitting some strings

Answer: C

Both generate every string over the two letters, including the empty one. This pair is the standard illustration that very differently written expressions can denote the same regular language. Only minimisation of the corresponding automata settles the question conclusively.

Discuss in Forum

84.

The complement of a regular language is

A.never regular at all, since complementation is not a regular operation
B.regular only when the original language is finite in size
C.regular only for languages over a single letter alphabet
D.always regular, obtained by swapping accepting and non-accepting states

Answer: D

Correct answer: always regular, obtained by swapping accepting and non-accepting states

Take a complete deterministic automaton for the language and exchange its accepting and non-accepting states: the resulting machine accepts exactly the strings the original rejected. The construction requires the automaton to be deterministic and complete, with a transition defined for every state and character, which is why a dead state is added first if one is missing.

Discuss in Forum

85.

The intersection of two regular languages is recognised by

A.the product automaton formed from the two deterministic machines
B.the union of the states of the two original automata
C.a pushdown automaton
D.concatenating the two automata end to end in sequence

Answer: A

Correct answer: the product automaton formed from the two deterministic machines

The product automaton has one state for each pair of states of the two originals and runs them side by side on the same input, accepting only when both would accept. Making the accepting condition “either” instead of “both” gives the union by the same construction, which is one way of showing regular languages closed under both.

Discuss in Forum

86.

Consider the following closure properties of regular languages.
1. closed under union
2. closed under concatenation
3. closed under complementation

A.1 and 2 only
B.All of them
C.None of them
D.1 only

Answer: B

Correct answer: All of them

Regular languages are closed under all three, and under intersection and difference besides. Union and concatenation follow directly from the regular expression operators; complementation follows from swapping accepting and non-accepting states of a complete DFA; and intersection then follows from the other two by De Morgan, or directly from the product construction.

Discuss in Forum

87.

A scanner generator combines the patterns for all tokens into

A.a context free grammar covering all the token definitions
B.a table of string comparisons applied to each candidate lexeme
C.a single automaton with an accepting state marked per pattern
D.one separate automaton per token, each run in turn on the input

Answer: C

Merging the patterns into one machine means the input is scanned once rather than once per token. The accepting state reached identifies which pattern matched, and rule order breaks any tie. One pass over the input therefore suffices no matter how many tokens are defined.

Discuss in Forum

88.

The chief practical advantage of a generated scanner over a hand written one is

A.the generated scanner always runs faster than any hand written one
B.generated scanners can recognise context free languages too
C.a generated scanner needs no interface to the parser at all
D.the specification is short, declarative and easy to change

Answer: D

Correct answer: the specification is short, declarative and easy to change

A Lex specification states what the tokens look like and leaves the construction of the automaton to the tool, so it is a fraction of the length of the equivalent code and can be changed by editing one pattern. A carefully hand-written scanner can be faster, so speed is not the argument; maintainability is.

Discuss in Forum

89.

A hand written scanner is sometimes preferred when

A.the language has unusual rules that patterns express awkwardly
B.the language has more than a hundred distinct token types
C.the compiler must be written in a purely functional language
D.the source alphabet contains fewer than sixty four characters

Answer: A

Correct answer: the language has unusual rules that patterns express awkwardly

Hand writing is chosen where the lexical structure does not fit the regular expression model comfortably - significant indentation, nested comments, string interpolation, or context-dependent rules such as Fortran’s insignificant blanks. Writing the awkward parts directly is often clearer than forcing them into patterns with elaborate actions and start conditions.

Discuss in Forum

90.

A lexical analyzer uses the following patterns to recognize three tokens T₁, T₂, and T₃ over the alphabet {a,b,c}.

\(T_{1}:\ a?\,(b|c)^{*}a\)
\(T_{2}:\ b?\,(a|c)^{*}b\)
\(T_{3}:\ c?\,(b|a)^{*}c\)

Note that 'x?' means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.

If the string \(bbaacabc\) is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

A.\(T_{1}T_{2}T_{3}\)
B.\(T_{1}T_{1}T_{3}\)
C.\(T_{2}T_{1}T_{3}\)
D.\(T_{3}T_{3}\)

Exam Year(s)

GATE CS - 2018,

Answer: D

The analyzer outputs \(T_{3}T_{3}\).

It always takes the longest prefix any pattern matches. On bbaacabc:

\(T_{1}\) can match bba (no leading a, then bb, then a): 3 characters.
\(T_{2}\) can match only bb, since \((a|c)^{*}\) cannot absorb the second b: 2 characters.
\(T_{3}\) can match bbaac (no leading c, then bbaa from \((b|a)^{*}\), then c): 5 characters.

So the first token is \(T_{3}\), for bbaac. The rest is abc: \(T_{3}\) matches all of it (ab, then c), while \(T_{1}\) matches only a and \(T_{2}\) only ab. So the second token is \(T_{3}\) too.

The options starting with \(T_{1}\) or \(T_{2}\) take a shorter prefix than the longest-match rule allows.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Lexical Analysis Questions and Answers || Lexical Analysis MCQ Questions and Answers || Lexical Analysis GK Questions and Answers || Lexical Analysis GK MCQ Questions || Lexical Analysis Multiple Choice Questions and Answers || Lexical Analysis GK || GK on Lexical Analysis || Compiler Design Questions and Answers || Compiler Design MCQ Questions and Answers || Compiler Design GK Questions and Answers || GK on Compiler Design

Lexical Analysis Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications