Finding the complement of a DFA?

As you says in question:

I know that to convert a DFA, M to the complement, M`, I just need to swap the initial accepting states and final accepting states.

Its not complement, but you are doing something like reverse of a language and regular languages are closure under reversal.

Reversal of DFA

What is the Reversal Language ?

The reversal of a language L (denoted LR) is the language consisting of the reversal of all strings in L.

Given that L is L(A) for some FA A, we can construct an automaton for LR:

  • reverse all edges (arcs) in the transition diagram
  • the accepting state for the LR automaton is the start state for A
  • create a new start state for the new automaton with epsilon transitions to each of the accept states for A

Note: By reversing all its arrows and exchanging the roles of initial and accepting states of a DFA you may get an NFA instead.
that’s why I written FA(not DFA)

Complement DFA

Finding the complement of a DFA?

Defination: The complement of a language is defined in terms of set difference from Σ* (sigma star). that is L‘ = Σ* – L.

And the complement language (L‘) of L has all strings from Σ* (sigma star) except the strings in L. Σ* is all possible strings over the alphabet Σ.
Σ = Set of language symbols

To construct the DFA D that accepts the complement of L, simply convert each accepting state in A into a non-accepting state in D and convert each non-accepting state in A into an accept state in D.
(Warning! This is not true for NFA’s)

A is DFA of L, D is for complement

Note: To construct complement DFA, old DFA must be a complete means there should all possible out going edge from each state(or in other words δ should be a complete function).

Complement: reference with example

Complement DFA for Regular Expression (00+1)*

below is DFA named A:

But not this DFA is not complete DFA. transition function δ is partially defined but not for full domain Q×Σ (missing out going edge from q1 for lable 1).

Its complete DFA can be as follows (A):

In the above DFA, all possible transactions are defined (*for every pair of Q,Σ *) and δ is a complete function in this case.

Reff: to learn what is Partial Function.

New complement DFA D can be constructed by changing all final states q0 to not final states and vice-versa.

So in complement q0 become non-final and q1, q2 are the final states.

Now you can write Regular expression for complement language using ARDEN’S THEOREM and DFA I given.

Here I am writing Regular Expression for complement directly:

(00 + 1)* 0 (^ + 1(1 + 0)*)

where ^ is null symbol.

some helpful links:
From here and through my profile you can find some more helpful answers on FA. Also, two good links on properties of regular language: one, second

Related Posts:

  1. OR condition in Regex
  2. Using or ‘|’ in regex [duplicate]
  3. What is a Context Free Grammar?
  4. What does \’.- mean in a Regular Expression
  5. How can I exclude one word with grep?
  6. How can I validate an email address using a regular expression?
  7. Regular expression to match a line that doesn’t contain a word
  8. Difference between \b and \B in regex
  9. Regex: ignore case sensitivity
  10. What does the regex \S mean in JavaScript?
  11. How can I validate an email address using a regular expression?
  12. Regex: ignore case sensitivity
  13. Python regex AttributeError: ‘NoneType’ object has no attribute ‘group’
  14. Regular Expression for alphanumeric and underscores
  15. What is the difference between the regular expressions [^\d\s] and [\D\S]
  16. Regular Expression for alphanumeric and underscores
  17. grep –ignore-case –only
  18. Regex AND operator
  19. python re.split() to split by spaces, commas, and periods, but not in cases like 1,000 or 1.50
  20. python re.split() to split by spaces, commas, and periods, but not in cases like 1,000 or 1.50
  21. Regular expression negative lookahead
  22. Regular Expression to match string starting with a specific word
  23. Regular Expressions: Is there an AND operator?
  24. Writing a very simple lexical analyser in C++
  25. Regular expression to match standard 10 digit phone number
  26. Regular Expression.how to add optional character at end of regex
  27. Regular Expression with wildcards to match any character
  28. What is a non-capturing group in regular expressions?
  29. Split string on whitespace in Python
  30. How to validate an email address in PHP
  31. What is a non-capturing group in regular expressions?
  32. Regular expression to match standard 10 digit phone number
  33. How to use Regular Expressions (Regex) in Microsoft Excel both in-cell and loops
  34. Python string.replace regular expression
  35. How to use Regular Expressions (Regex) in Microsoft Excel both in-cell and loops
  36. Python string.replace regular expression
  37. Grep and Python
  38. Regex – Does not contain certain Characters
  39. How to replace ” \ ” with ” \\ ” in java
  40. A regular expression to exclude a word/string
  41. Regex how to match an optional character
  42. How to validate an email address in JavaScript
  43. Using Bash regex match (=~) where regex includes quotes (” characters)
  44. Searching for UUIDs in text with regex
  45. Regular expression for exact match of a string
  46. Using the star sign in grep
  47. Regex optional group
  48. Regex for string contains?
  49. Question marks in regular expressions
  50. Difference between \w and \b regular expression meta characters
  51. Regular Expression – Validate Gmail addresses
  52. Java; String replace (using regular expressions)?
  53. How can I remove punctuation from input text in Java?
  54. How can I output only captured groups with sed?
  55. How to negate specific word in regex?
  56. What is the grep equivalent in Python?
  57. Which regular expression operator means ‘Don’t’ match this character?
  58. Python re.split() vs split()
  59. How can I write a regex which matches non greedy?
  60. Regex Explanation ^.*$ [duplicate]
  61. How to exclude a specific string constant?
  62. How to replace a whole line with sed?
  63. Regex match everything after question mark?
  64. Validating IPv4 addresses with regexp
  65. How to validate phone number using PHP?
  66. Validate phone number with JavaScript
  67. Can a URL contain a semicolon and still be valid?
  68. Regex to match only uppercase “words” with some exceptions
  69. Regex to match only letters
  70. Regex optional capturing group?
  71. RegEx to find two or more consecutive chars
  72. Regex to match an optional ‘+’ symbol followed by any number of digits
  73. Regular expressions in C: examples?
  74. How to ignore whitespace in a regular expression subject string?
  75. Regex: matching up to the first occurrence of a character
  76. Regex credit card number tests
  77. Regular expression – starting and ending with a character string
  78. How do I match any character across multiple lines in a regular expression?
  79. Regular expression to limit number of characters to 10
  80. Regex that matches integers in between whitespace or start/end of string only
  81. Regular Expressions- Match Anything
  82. What is the difference between square brackets and parentheses in a regex?
  83. Regex for “AND NOT” operation
  84. Regular expression that matches valid IPv6 addresses
  85. Escaping Parentheses in Regex
  86. How to replace a string in an existing file in Perl
  87. What is the best regular expression to check if a string is a valid URL?
  88. Regex empty string or email
  89. Regex difference: (\w+)? and (\w*)
  90. Wrap element with in any number of elements with PHP
  91. extract shortcodes from string
  92. preg_replace and comment_form_defaults
  93. How to set up redirects for category paginated pages after adding /category/ to permalink
  94. Adding span tags to post titles using regex
  95. Redirect non www to www using redirection plugin regex
  96. Restrict comments with regular expression
  97. Call Shortcode Attribute Value within another function
  98. How to fix old embeded iframes with WP-CLI search-replace
  99. Regex For Extracting First 4 letters of search term
  100. Use Regex Redirection via htsaccess for RSS Feeds WordPress

1 thought on “Finding the complement of a DFA?”

  1. whoah this blog is wonderful i really like reading your articles. Keep up the great paintings! You realize, a lot of people are hunting round for this info, you could help them greatly.

    Reply

Leave a Comment