Suppose $$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n \text{ or} |w|=n\}$$ Can we conclude that $L$ is DCFl?

I think it's DCFL because $$L=\{a^no^n\}\cup \{\{a,b\}^no^n\}$$ Since $$\{a^no^n\}\subseteq \{\{a,b\}^no^n\}$$ We can coclude that $L$ is DCFL. Becuase $$L= \{\{a,b\}^no^n\}$$

But i think my argument, maybe isn't true, anyone can approve my argument or disprove my argument?

  • 2
    $\begingroup$ It's not true that $L=\{a^no^n\}\cup \{\{a,b\}^no^n\}$. You can also accept e.g., the word aaabbooo (since the number of a's is the same as the number of o's). $\endgroup$
    – Shaull
    Jul 31, 2021 at 14:17
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Jul 31, 2021 at 16:23
  • 1
    $\begingroup$ No, your language seems not to be DCFL. I do not know what tools you are familiar with that allow one to show that fact. For DCFL one may use specific closure properties, or a pumping lemma. $\endgroup$ Jul 31, 2021 at 23:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.