Construct a DFA of the language L = { L1 \ L2 }
How can I construct a DFA of the language L = { L1 \ L2 }
The DFA's of L1 and L2 are given, but how can I "substract" one DFA from another? Is this somehow possible with the relative complement http://en.wikipedia.org/wiki/Complement_(set_theory) and DeMorgans Law?
My solution:
To my understanding, the desired DFA can be obtained by using a modified product automaton, as used for the intersection of L1 and L2, but the terminal states have to be defined differently. Instead of making a product state (q_1,q_2) a terminal state if and only if q_1 and q_2 are terminal states in A(L1) and A(L2) respectively, define it to be a terminal state if and only if q_1 is a terminal state and q_2 is not a terminal state.
I'm not quite sure if besides this elementary argument, the result can be applied by the set formulation of De Morgan's law.
- How do you construct the union of two DFAs?
- Regular Expression for Binary Numbers Divisible by 3
- Steps to draw a DFA (or NFA) from a simple statement?
- Are my DFA's correct? (arbitrary long sequence of 0's and 1's)
- DFA for all binary strings having even number of 0's or contains exactly two 1's
- Create a DFA that contains "11" or ends with "10"
- Theory of computer science problems
- a challenging finite automata - what is the language?
- State diagram of DFA with 5 states
- Am I correct? (Finite Automata)
- What strings are accepted by the pattern "^[ab]?|c?$"?
- Conversion of NFA having a missing transition for any input character on initial state to DFA
- Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
- Regular Expression for Automata for Strings that do not end in 01
- DFA- Set of all strings whose 10th symbol from the right end is 1
- NFA or DFA accepting # of positions of 4k between 0's
- Minimum number of states in a DFA having '1' as the 5th symbol from right
- Why do we use pumping lemma to prove the non-regularity of languages? WHY?
- can a DFA have an arrow with empty string as input?
- Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language
- Parser vs. lexer and XML
- Can all context free grammars be converted to NFA/DFA?
- Design DFA accepting decimal strings divisible by 7
- Is L = {a^n a^n b^m |m, n ≥ 0} a regular or irregular language?
- Are those two regular languages the same?
- NFA to DFA conversion = deterministic?
- Regular Expression to DFA
- DFA that will accepts the string having odd number of 1's and odd number of 0's
- How to find longest accepted word by automata?
- How to apply Kleene star on automata?