State 1: Initial state. If it gets a 'b' at first then there may be a possibility that it belongs to b*a* but can never be a part of anbm where n,m>0.
If it gets an 'a' then it can be part of b*a* (taking 0 instances of b) or may belong to anbm where n,m>0.
If it gets Null( which is also part of L1 union L2) then we will accept it by empty stack way.
We therefore separate the paths.
On getting 'b' it will go to State 5.
On getting 'a' it will stay in State 1.
On getting nothing we will go to State 4.
State 1 keeps on accepting a's and keep counting it's number until we get a 'b'. For each 'a' we push 'a' onto the stack.
Once we get b we shift to State 2 popping one 'a' from stack.
State 2:
We know that to reach here the string must have been aa*b till now.
Now here we keep on popping 1 a for each b. For m ≠ n there can be only 2 possible situations :
1) If m>n then once we reach the end of the string there will still be (m-n) a's left in the stack as all the n b's have popped n a's.
In that case we shift to State 4 on ∈. The transition wil be : On reaching the end of the string (∈) if still we see a as TOS symbol then we move from State 2 to State 4 and pop the a.
We keep on popping a until we see Z0(initial stack symbol). -- (∈,a/∈)
On seeing Z0 we pop that too (∈,Z0/∈) // Accepting by empty stack
2)If m<n, then there will be no a's present in the stack but the string is still left with (n-m) b's.
The TOS is Z0 as all the m a's have been popped off. So we move to State 3 on (b,Z0/Z0).
State 3: we keep on getting b's and do nothing(no pop or push). Once we reach the end of string then pop Z0 (∈,Z0/∈) // Accepting by empty stack
Now we need to check for strings of b*a* form. This can generate strings like ∈,a*,b*,ba,bbaa,bbbaa....
So again we look back to State 1.
-->If we get ∈ then we directly go to State 4 on (∈,Z0/∈).
-->If we get aaa..a followed by no b's (i.e. strings containing only a's) then also send it to State 4 on (∈,a/∈). We have already discussed what happens in State 4.
-->If we get b as the first character then send it to State 5 on (b,Z0/Z0). We don't need to remember the count of b's and a's so we don't perform any push or pop. Simply keep on taking each character. If we get a then move to State 6 on (a,Z0/Z0). If we get Epsilon the also move to State 6 on (∈,Z0/∈).
NOTE: This might not be a minimized DPDA.
Since L is a DPDA so L' is also a DPDA ( DCFLs are closed under complementation).
Replying to your comment :
1) Intersection of Reg with any other language dcfl,cfl,rec,re is dcfl,cfl,rec,re respectively. The way you did like promoting Reg to DCFL as all Regs are also DCFLs won't work here. There have been multiple users including me with such confusion. But others tried helping us to clear this. If you think that Reg intersection DCFL may not be DCFL then think of one example to justify that.
2) When the question provides us with some specific language it is not safe to deduce like that. This is because what you got is "DCFL intersection DCFL" may or may not be a DCFL. But we can't say that it is definitely not a DCFL. What if the language given in the question falls in the "MAY BE a DCFL" part?
P.S. These were my suggestions based on my experience(I am a student so you may not rely on it :P). I would also like you to suggest me if you find flaws in the DPDA because I might have done mistakes :P
