0
$\begingroup$

Is odd length pallindrome DCFL or NCFL?

Like

1) $L=\{w1w^R\mid w \in \{0, 1\}^*\}$

or

2) $S\rightarrow aSa\mid bSb\mid a$

or

Suppose odd length String like

3)$S\rightarrow aSa\mid bSb\mid aSb\mid bSa\mid a\mid b$

We get information about even length palindrome, that it can never be DCFL, but what about odd length?

$\endgroup$
  • 1
    $\begingroup$ Is the question supposed to be a multiple-choice question between alternatives 1, 2, and 3? Also, what is "string" referring to in the question title? I am confused. $\endgroup$ – dkaeae Dec 18 '18 at 7:15
  • $\begingroup$ No, all three are different string. I want to know any DCFL exists among them? I am getting trouble to find DCFL among them. Actually all of them almost same type grammar. and 3rd one not pallindrome but odd length CFL. So, are they DCFL? $\endgroup$ – Srestha Dec 18 '18 at 9:51
  • 1
    $\begingroup$ Do you mean "language" instead of "string"? A string cannot be a DCFL because it is an element of a language, not a language itself. $\endgroup$ – dkaeae Dec 18 '18 at 10:14
  • 1
    $\begingroup$ Also, you seem to be mistaking a grammar for a language. Grammars generate languages, but they are not languages themselves. I recommend you go over the definitions again and try to neatly separate the concepts in your mind. $\endgroup$ – dkaeae Dec 18 '18 at 10:20
0
$\begingroup$

Hint: The DCFL among the three alternatives is not only a DCFL, it is a regular language.

(Recall that the regular languages form a subset of the DCFLs.)

Hint no. 2: The other two alternatives are essentially the same language, only over different alphabets.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Srestha If you know what a DCFL is, I am sure you are also aware of what a regular language is. I believe my hints are generous enough; your question looks like a homework assignment, so I am afraid you will not get any more from me than that. $\endgroup$ – dkaeae Dec 18 '18 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.