Skip to main content
Changed the question to agree with the reformulation in the comments; deleted 6 characters in body
Source Link
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a deterministic context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a deterministic context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

Tidied up a bit, and made question's title more explicit; removed second sub-question.
Source Link

Context Are context-free languages and complementation: Closure and Interiorwith context-free complements necessarily deterministic context-free?

I'm not sure if "interior" is the right word, but hopefully its usage will be motivated by the following question.

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a deterministic context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

I have another, related question, in a similar vein to above, but perhaps dual - addressing the "closure" I described in the title.

The context-sensitive languages are closed under finitary Boolean operations, in particular complementation, but the context-free languages are not closed under complementation or intersection.

Is the class of languages formed by taking finitary sequences of union, intersections and complements of context-free languages the class of context-sensitive languages - i.e. the closure under these operations?

That is, is every context-sensitive language $L$ generated from a finite set $\{L_1, \ldots, L_n\}$ of context-fre languages by taking unions, intersections and complements?

Context-free languages and complementation: Closure and Interior

I'm not sure if "interior" is the right word, but hopefully its usage will be motivated by the following question.

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a deterministic context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

I have another, related question, in a similar vein to above, but perhaps dual - addressing the "closure" I described in the title.

The context-sensitive languages are closed under finitary Boolean operations, in particular complementation, but the context-free languages are not closed under complementation or intersection.

Is the class of languages formed by taking finitary sequences of union, intersections and complements of context-free languages the class of context-sensitive languages - i.e. the closure under these operations?

That is, is every context-sensitive language $L$ generated from a finite set $\{L_1, \ldots, L_n\}$ of context-fre languages by taking unions, intersections and complements?

Are context-free languages with context-free complements necessarily deterministic context-free?

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a deterministic context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

Source Link

Context-free languages and complementation: Closure and Interior

I'm not sure if "interior" is the right word, but hopefully its usage will be motivated by the following question.

Let $L \subseteq A^\star$ be a formal language over $A$ generated by a deterministic context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.

If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?

I have another, related question, in a similar vein to above, but perhaps dual - addressing the "closure" I described in the title.

The context-sensitive languages are closed under finitary Boolean operations, in particular complementation, but the context-free languages are not closed under complementation or intersection.

Is the class of languages formed by taking finitary sequences of union, intersections and complements of context-free languages the class of context-sensitive languages - i.e. the closure under these operations?

That is, is every context-sensitive language $L$ generated from a finite set $\{L_1, \ldots, L_n\}$ of context-fre languages by taking unions, intersections and complements?