1,691 views
7 votes
7 votes
A = { <M> | M is a DFA that accepts some string with more 1s than 0s }. Then A is -

a) undecidable

b) recursive enumerable

c) decidable

d) none of the above

3 Answers

6 votes
6 votes

1.   $A = \{ <M> | M $ is a $DFA$ that accepts some string with more 1s than 0s $ \}.$

Decidable.

Logic:

Create a PDA $P$ for β€œ$L(P)$ = More 1’s than 0’s” language.

For given DFA $M,$ Create a PDA $N$ for $L(P) \cap L(M)$ (We can do this as we know that CFL intersection Regular = CFL

Check if $L(N)$ is Empty or Not. (Emptiness of CFLs is Decidable)


2.   $A = \{ <M> | M $ is a $DFA$ that accepts EVERY(any) string with more 1s than 0s $ \}.$

Decidable.

Logic:

Create a DPDA $D$ for β€œ$L(D)$ = More 1’s than 0’s” language.

For given DFA $M,$ Create a DPDA $N$ for $L(D) \cap L(M)$ (We can do this as we know that DCFL intersection Regular = DCFL

Check the Equivalence of $D, N$. (Equivalence of DCFLs is Decidable)


NOTE:

From GATE exam point of view:

In $99.99% $ cases, If the question is about deciding some property of Regular Languages, then it is Decidable. 

In $99.99% $ cases, If the question is like β€œGiven a FA $M$, Does $L(M)$ have some property $P$”, then it is Decidable. 

There are some Undecidable problems concerning Regular Languages, BUT those are of Research Level, NOT of basic automata theory level..

So, For GATE exam, you can consider that All properties of Regular Languages are Decidable. 

https://cs.stackexchange.com/questions/81542/undecidable-problem-for-regular-languages


To UNDERSTAND β€œTheory of Computation”, To Understand topics like β€œDecidability” etc with $\color{red}{\text{Crystal Clear Understanding:}}$ 

Join GO Classes TOC Course:

https://www.goclasses.in/courses/Theory-of-Computation-2023 

Or Join GO Classes GATE CSE Complete Course:

https://www.goclasses.in/s/pages/gatecompletecourse 

edited by
1 votes
1 votes
We can construct a Turing Machine Decider for A like :
  
 T = "On input <M> where M is encoded DFA"
    1. Construct a another DFA say, N such that L(N)={w|w has more 1s than 0s}
    2. For each input x
       a. if( x is accepted by DFA M){
              if(accepted by N){
               "accepted" and return;
              }
    3. "rejected"

So, A is decidable.
0 votes
0 votes

DECIDABLE

First let 'u' belongs to TM encoded on 0's & 1's. If u does not belong to a DFA ( we reject it)
If  u belongs to a DFA  we check for Strings with more 1's than 0's. If DFA accepts it belongs to A
Else we reject.
Likewise we can accept all the TM which accepts Strings with more 1's than 0's 
So Algo accepts strings that belong to language & reject the ones which do not accept it.
Hence Decidable

edited by
Answer:

Related questions

1 votes
1 votes
0 answers
1