# Tag Info

Accepted

### Union of regular languages that is not regular

There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L_{1}, L_{2}, \ldots$ such ...
• 17.7k
Accepted

• 80.2k
Accepted

### Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Yes you are on right track. We can first define ($A$ avoids $B$) as ($A$ - ($A$ has $B$)), where ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings. Then ($A$ avoids $B$) ...
• 4,747
Accepted

### Constructing all context-free languages from a set of base languages and closure properties?

That is possible, but perhaps not exactly in the way you ask. As a start take the Dyck language $D_2$ of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$, or more ...
• 27.6k
Accepted

### Are DCFLs closed under reversal?

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter. Searching the web does also give a ...
• 19.1k
Accepted

### How to XOR automata?

Note that the construction for the intersection and union ("and" and "or") of two automata is exactly the same, except for the definition of which states are accepting. The same principle applies to ...
• 80.2k
Accepted

### Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

The notion of a PDA can be generalized to an $S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of a read-only input tape, surrounded by endmarkers, a finite state control, a read-write ...
• 5,322
Accepted

### Why is the set of all regular expressions classified as context-free, instead of regular?

Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?" The reason is simply the ...
• 2,148
Accepted

### Show that P is closed against the Kleene star

Hint: Use dynamic programming. If the input is $x_1 \ldots x_n$, compute inductively whether $x_1 \ldots x_i \in L^*$. Use the fact that you can check whether $x_{j+1} \ldots x_i \in L$ in polynomial ...
• 270k
Accepted

• 141k