0 votes 0 votes Complementation of DFA works for all DFA is it true ? Given DFA, a should be followed by a 'b', In the complementation of this DFA the string aab is getting accepted a is getting followed by a 'b' Theory of Computation finite-automata theory-of-computation + – sanju77767 asked Mar 18, 2018 • edited Mar 18, 2018 by Devshree Dubey sanju77767 943 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Mk Utkarsh commented Mar 18, 2018 i edited by Mk Utkarsh Mar 18, 2018 reply Follow Share Dfa where every "a" is followed by a "b" "Every a" is followed by a "b" but when you complement this DFA some a can be followed by b but not all 1 votes 1 votes sanju77767 commented Mar 18, 2018 reply Follow Share But then how can we say then that it is fully complemented if the dfa is every 'a' should be followed by a 'b' and if we complement that the DFA 'a' should never be followed by 'b' that too I can understand some of 'a' will be followed by 'b' these some strings should not be there then only the dfa will be complemented l={epsilon,b,bb,bbb} these strings are common strings for both the DFA because they are not containing a 0 votes 0 votes ankitgupta.1729 commented Mar 18, 2018 reply Follow Share @Utkarsh , but in question , it is not mentioned that every 'a' should be followed by 'b' 0 votes 0 votes Mk Utkarsh commented Mar 18, 2018 reply Follow Share sanju77767 ok listen the DFA accepts all strings in which every a is followed by a b, that's called a regular set. Complement that set. What we got now? we got $\sum$* - regular set. Which is also regular. So that set will contain all strings of $\sum$ but not the ones which are in our previous regular set. for example we get aab,aaaab,abaa all these strings were not generated by our DFA so they are generated by its complement 0 votes 0 votes Mk Utkarsh commented Mar 18, 2018 i edited by Mk Utkarsh Mar 18, 2018 reply Follow Share ankitgupta.1729 then we don't know which a is followed by b and which doesn't. ambiguous statement that means then it can accept all strings from $\sum$ = {a,b} and complement is empty set $\left \{ \phi \right \}$ 1 votes 1 votes Mk Utkarsh commented Mar 18, 2018 reply Follow Share l={epsilon,b,bb,bbb} these strings are common strings for both the DFA because they are not containing a These strings were accepted by our DFA because there is no "a" in it. Question gave the conditions for only "a", so epsilon and all strings containing only b are accepted but its complement cannot accept this because of the definition of compliment 0 votes 0 votes sanju77767 commented Mar 18, 2018 reply Follow Share @utkarsh hiii thank u for clarifying I'm studying TOC first time so sry If I ask silly questions complement of language and complement of DFA is different or same plzzz clarfy this statement question is every 'a' should be followed by a 'b' if we complement that every 'a' should never be followed by 'b' the strings which are not accepted by original DFA......... it will be accepted by its complement k that I understood but the strings which are intersect between both DFA's what about them they are also not acceptd by DFA's complement aaaab ,aab, these strings are not accepted by original DFA , and in its complement a is followed by b then it can't be the proper complement of the DFA its the dilemaa 0 votes 0 votes Mk Utkarsh commented Mar 18, 2018 reply Follow Share proper complement? never heard of that. which strings intersect btw both the DFA's? I would suggest you that read and solve 1-4 chapters of Peter Linz. You will feel confident with this topic. 0 votes 0 votes sanju77767 commented Mar 18, 2018 reply Follow Share Kk I'll read Peter Linz book and intersect string are L ={€,b,bb,bbb,. } These strings should be common in both the Dfa's 0 votes 0 votes Mk Utkarsh commented Mar 18, 2018 reply Follow Share these string are accepted in 1st DFA then complement will not accept these strings 0 votes 0 votes sanju77767 commented Mar 18, 2018 reply Follow Share Yes u r write but if we write the languages for both the strings seperately then these strings will be comman in both DFA's 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes at most one possibility does not occur , Like, when will be ∀ false ? when we show a single counter example , right? and yes the complement of "every a is followed by a b" is true , when we show a single counter that that does not occur rajsh3kar answered Mar 18, 2018 rajsh3kar comment Share Follow See all 0 reply Please log in or register to add a comment.