The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
2.2k views

Consider the DFA A given below.

Which of the following are FALSE?

  1. Complement of $L(A)$ is context-free.
  2. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*) $
  3. For the language accepted by $A, A$ is the minimal DFA.
  4. $A$ accepts all strings over $\{0, 1\}$ of length at least $2$.
  1. 1 and 3 only
  2. 2 and 4 only
  3. 2 and 3 only
  4. 3 and 4 only
asked in Theory of Computation by Veteran (355k points)
edited by | 2.2k views

2 Answers

+45 votes
Best answer
  1. Complement of $L(A)$ (regular language) is regular , i.e also Context Free. True 
  2. Regular expression is $(11^*0 +0)(0+1)^*$  True 
  3. Minimized DFA is:     
    [both non-final states are equivalents can be minimized]
    So, $3$ is False 
  4. From $3$, shortest length string reached from $q0$ to $q1$ (final) is $0$, so $4$ is False 

Note :

  1. $(0+1)^*0^*1^* = (0+1)^* + \text{something} =(0+1)^*$
  2.  $(11^*0+0)(0+1)^* = (11^*+ $^ $)0(0+1)^* =1^*0(0+1)^*$ look at Minimized DFA at $3$.
answered by Veteran (55k points)
edited by
+3

@Praveen Saini   Sir, in 

a) (0+1)*0*1* = (0+1)* +something =(0+1)*

 

Sir, in (0+1)*0*1* ---> 0*1* is getting multiplied, but here you've written + in (0+1)*+something. 

Sir, which property is this? How did you write this?

+7
$(0+1)^*\{\epsilon ,0,00,......\}\{\epsilon ,1,11,......\}$

$(0+1)^*\{\epsilon ,0,00,......1,11.....01,011,......001,0011,....\}$

$(0+1)^*+(0+1)^*0+(0+1)^*00+......+(0+1)^*1+(0+1)^*11+.....$
0
@Praveen Saini Sir, How the first statement under Note is True?
0
@anchit as in comment as above.
–6 votes
4: a single 0 is also accepted thats why 4 is false 1:the complement is also a reg lang 2 and 3 are correct
answered by Boss (14.2k points)
Answer:

Related questions



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

37,942 questions
45,453 answers
131,195 comments
48,213 users