retagged by
770 views
1 votes
1 votes

Consider any arbitrary DFA M of your choice and Let the language accepted by some DFA M be L. Let L1 be the language accepted by the DFA M1 obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting states of M to accepting states. Which of the following statements is true?

  1. L1={0,1}∗−L
  2. L1={0,1}∗
  3. L1⊆L
  4. L1=L
retagged by

2 Answers

Best answer
2 votes
2 votes

When ever we change all final states to non final and all non final to final states ,then we get the complement of the DFA.And in case of DFA the language accepted by the complement DFA is the complement of the language accepted by the actual DFA.

So M here accepting language L. And the complement DFA M1 will accepts language L1.Now as per above statement L1 is complement of L.

So L1=L' =(0+1)*-L // Assuming that language is defined over 0,1.

So a is correct answer here.

Remeber that this does not hold true in NFA.It will hold in NFA only if that NFA is a DFA. 

selected by
1 votes
1 votes
Nothing mentioned about the input symbols.

Assuming the input symbols as {0,1} , the answer is (a).

Related questions

0 votes
0 votes
1 answer
1
gateexplore asked Jun 11, 2023
412 views
Construct an NFA that will accept string of 0's, 1's and 2's beginning with a 0's followed by an odd number of 1's and ending with any number of 2's. Please give the answ...
3 votes
3 votes
1 answer
2
abhinowKatore asked Jan 14, 2023
531 views
Please explain what is difference between $\overline{L(N)}$ and $L(\overline{N}$) ?
0 votes
0 votes
1 answer
3
atulcse asked Jan 21, 2022
830 views
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
3 votes
3 votes
2 answers
4
Hirak asked May 22, 2019
2,313 views
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ?(a) 4 (b) 16 (c) 20 ...