in GATE
4,680 views
7 votes
7 votes

The following Finite Automaton recognizes which of the given languages?

  1. $\{ 1, 0 \}^* \{ 0 1 \}$
  2. $\{ 1,0\}^*\{ 1\}$
  3. $\{ 1 \} \{1, 0\}^*\{ 1 \}$
  4. $1^*0^*\{0,1\}$
in GATE
4.7k views

5 Answers

7 votes
7 votes
Best answer
Option A] is the answer.

How ?  Try each option.Validate strings in given FA. start from small strings.
edited by

4 Comments

.. sry .. i understood..
0
0
why not D?
0
0
the string should contain 01 but in option D it will end with 0 or 1.
0
0
from {1,0} * we can also have string starting from 0 and that string will not be accepted

So D should be ans not A

any comments ?
0
0
2 votes
2 votes
yes A is the ans

eliminate all other ..how check

B.{ 1 } is not accepted by the fa.

c.{1}{1} is not accepted by fa

d.{0} is not accepted

with opt A .all strings generated can be accepted
by
1 vote
1 vote
Given DFA accepts all strings ending with "01", so the language should be (0+1)*01. Option (A) is correct,
edited by
by
0 votes
0 votes
D. 1*0*(0+1), only 0 only 1 not accepted hence it's false

C. 1(1+0)*1, 11 is the invalid string for here also false

B.(1+0)*1, same as option D 1 is rejected by FA

A. (1+0)*(01) genrate language like {01,101,1101,1001,0101,0001,11101,11001,10001,01101.....} all are accepted by above FA so it's correct.
edited by

1 comment

@Hira Thakur Sir, as you have written option A is (1+0)*(0+1) should be as (1+0)*01

bcoz(1+0)*(1+0) gives us only '1' and only '0' stings also.

plz correct me if im wrong...

2
2
Answer:

Related questions