Question 1 |

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:

letter \rightarrow [A-Za-z]

digit \rightarrow [0-9]

id \rightarrow letter (letter\;| \;digit)^*

Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

letter \rightarrow [A-Za-z]

digit \rightarrow [0-9]

id \rightarrow letter (letter\;| \;digit)^*

Which one of the following Non-deterministic Finite-state Automata with - transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

A | |

B | |

C | |

D |

Question 1 Explanation:

Question 2 |

Consider the Deterministic Finite-state Automaton (DFA) A shown below. The
DFA runs on the alphabet {0, 1}, and has the set of states {s, p, q, r}, with s being
the start state and p being the only final state.

Which one of the following regular expressions correctly describes the language accepted by A?

Which one of the following regular expressions correctly describes the language accepted by A?

1(0^*11)^* | |

0(0 + 1)^* | |

1(0 + 11)^* | |

1(110^*)^* |

Question 2 Explanation:

Question 3 |

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string \epsilon is divisible by three.

**[MSQ]**(0+1(01^*0)^*1)^* | |

(0+11+10(1+00)^*01)^* | |

(0^*(1(01^*0)^*1)^*)^* | |

(0+11+11(1+00)^*00)^* |

Question 3 Explanation:

Question 4 |

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?

((0+1)^* 1(0+1)^*1)^*10^* | |

(0^*10^*10^*)^*0^*1 | |

10^*(0^*10^*10^*)^* | |

(0^*10^*10^*)^*10^* |

Question 4 Explanation:

Question 5 |

In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

(L+D)^{+} | |

\text { (L.D)* } | |

L(L+D)^{*} | |

L(L . D)^{*} |

Question 5 Explanation:

There are 5 questions to complete.

Options wrong

Please specify the question number and option which you fell as wrong.

7th C option is wrong

Thank You shivam,

We have updated the option C.

Useful.Thank you

Q11 options A and B don’t have a final state.

Thank You,

We have updated the figure as per your suggestion.

In question 14 c and d options are the same

We have updated the image.

In question 14 option (a), figure is incomplete (there should be loop(a,b) over S3 ).