The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

How to solve these type of questions please explain?

asked in Theory of Computation by Active (1.2k points) | 51 views

2 Answers

0 votes

Method 1 : Eliminating Options

The fastest way would be "Eliminating Options".
Here, RE $II$ can be eliminated by Taking String $10101$..which is accepted by the FA in Diagram But not generated by RE $II$.

So, You can eliminate Options $A,C,D$ as they have RE $II$. 

This method can only be used to Eliminate options, Not for Selecting correct Option. This method is based on the quote/expression "When you have eliminated the impossible, Whatever remains however improvable must be the Truth".. 

We were lucky that Three Options got eliminated here in this Question. But this would not be the case everytime, So, Knowing correct logic is required.

Method 2 : Sense the Language of the FA :(Best method if we can)

With lots of practice, we can make ourselves able to sense the language of the FA in most questions. 

Here, It is a Standard FA which accepts the language "Ending with $1$" . So, Answer would Option B as RE $I$ and $III$ generate the language "Ending with $1$"

Method 3 : Convert the FA into RE using Boring and lengthy algorithms

Knowing every algorithm in the syllabus surely helps sometimes. Here also, You could just use the "FA to RE" algorithm and get the answer. The one drawback of this method is that algorithm will give 1 or 2 RE But maybe none of them are in the options. Here,in our question, It is not the case. So, Apply this method and see.

answered by Boss (17.5k points)
0 votes

duplicate question.please close it

answered by Active (4.1k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,106 questions
45,610 answers
49,238 users