Find dfa’s that accept the following languages:(a) L = L (ab∗a∗) ∪ L ((ab)∗ ba).
Question
Find DFA's that accept the following languages:
- L = L (ab∗a∗) ∪ L ((ab)∗ ba)
Solution
Sure, let's break down the problem into two parts according to the union operation in the language definition.
(a) L = L (ab* a*)
This language accepts strings that start with 'a', followed by zero or more 'b's, and then followed by zero or more 'a's. Here is the DFA:
State Q0 is the start state. When we get 'a' in Q0, we move to Q1. In Q1, we can either get 'b' and stay in Q1 or get 'a' and move to Q2. In Q2, if we get 'a', we stay in Q2. Any other input will lead to a dead state. Q2 is the only final state.
(b) L = L ((ab)* ba)
This language accepts strings that have zero or more 'ab' pairs, followed by 'ba'. Here is the DFA:
State Q0 is the start state. When we get 'a' in Q0, we move to Q1. In Q1, if we get 'b', we move to Q2. In Q2, if we get 'a', we move to Q3. In Q3, if we get 'b', we move to Q4. Any other input will lead to a dead state. Q4 is the final state.
Now, to create a DFA that accepts the union of these two languages, we need to create a new start state and add epsilon transitions from this new start state to the start states of the two DFAs we created above. The final states of the new DFA are the final states of the two original DFAs.
Similar Questions
For two languages A and B, let there be DFAs of k1 and k2 states respectively. Then, A union B has a DFA with at most __ states1 pointk1+k2k1k2k1^k2k1/k2
NFA doesn’t require to show transitions for all input symbols in alphabet set over a statea.trueb.false
Find regular grammars for the following languages on {a, b}:(a) L = {w : na(w) is even, nb(w) ≥ 4}
NFA doesn’t require to show transitions for all input symbols in alphabet set over a statea.falseb.true
Which of the following can accept even palindrome over {a,b}ans.Turing machinePush down AutomataNDFAAll of the mentioned Previous Marked for Review Next
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.