GATE CSE 2023 | Question: 9

Question

Consider the following definition of a lexical token $\textbf{id}$ for an identifier in a programming language, using extended regular expressions:
\[
\begin{array}{ll}
\textbf{ letter } & \rightarrow[\mathrm{A}-\mathrm{Za}-\mathrm{z}] \\
\textbf{ digit } & \rightarrow[0-9] \\
\textbf{ id } & \rightarrow \textbf{ letter }(\textbf{ letter } \mid \textbf{ digit })^{*}
\end{array}
\]
Which one of the following Non-deterministic Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

• A.
• B.
• C.

• D.

Comments

Detailed Video Explanation:

Lexical Analysis & NFA question (Digit, Letter)

---

isn’t there an option like this in the exam? I remember an option like this and I’ve put this as the answer.

---

A accepts epsilon, but ques says it should atleast accept letter
B cannot accept strings like this :- letter letter digit digit OR letter digit letter letter
D  cannot accept :- letter letter letter OR letter digit

C can accept :-  letter  ( letter + digit )*

---

https://gateoverflow.in/2596/gate-cse-1995-question-1-9-isro2017-13
related qn

Answer 1

The regular expression is given as $\text{letter(letter+digit)*}$.

This regular expression accepts the strings of one occurrence of a letter followed by any occurrence of letter and digits, such as $\text{(letter,letter.letter,letter.digit,letter.digit.digit..$\infty$)}$

Option (A) This is wrong because it also accepts empty string that is  $\epsilon$.

 

Option (B): 

This is wrong because it accepts strings like $\text{(letter), (letter.letter) ...(letter.digit) ,(letter.digit.digit)}$, but it will not accepts the strings like $\text{(letter.digit.letter)}$. 

Option (C): It is the correct option. it will accepts all the strings of $\text{letter(letter+digit)*}$.

Option (D):

it is wrong. it RE is $\text{(letter(letter. digit)*)}$

and it will accept strings like ${(letter),(letter.letter.digit).(letter.letter.digit.letter.digit)...\infty}$.

 it will not accepts strings like $(letter. letter),(letter. digit)$ etc.

Comments

helpful..

---

in option A if we did not have epsilon transition, then would it have been a correct NFA?

---

yes then it will be true

Answer 2

Detailed Video Solution:

GATE CSE 2023 - Lexical Analysis & NFA question (Digit, Letter)

Answer 3

The regular expression is given as $\text{letter(letter+digit)*}$.

This regular expression accepts the strings of one occurrence of a letter followed by any occurrence of letter and digits, such as $\text{(letter,letter.letter,letter.digit,letter.digit.digit..$\infty$)}$

Option (A):

This is wrong because it accepts strings like $\text{(letter), (letter.letter) ...(letter.digit) ,(letter.digit.digit)}$, but it will not accepts the strings like $\text{(letter.digit.letter)}$. 

Option (B): It is correct.

Option (C):

it is wrong. it RE is $\text{(letter(letter. digit)*)}$ and it will accept strings like ${(letter),(letter.letter.digit),(letter.letter.digit.letter.digit)...\infty}$.

 it will not accepts strings like $(letter. letter),(letter. digit)$ etc.

Answer 4

A is wrong bcoz it is accepting null.

B is wrong bcoz what if letter digit letter comes.

D is wrong bcoz letter digit is not accepted.

C is correct.

Answer 5

Option C