As of May 31, 2023, we have updated our Code of Conduct.

# Tag Info

Accepted

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$) ...
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 ...
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 ...
Accepted

### Why does the concatenation of the empty set with any language give the empty set?

Let $L_1, L_2$ be languages, then the concatenation $L_1\circ L_2=\{w\mid w=xy, x\in L_1, y\in L_2\}$. If $L_2=\varnothing$, then there is no string $y\in L_2$ and so there is no possible $w$ such ...
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 ...
Accepted

Accepted

Accepted

### If L is regular, show that even(L) is also regular

We can also solve this question using closure operations. Let $\Sigma$ be the original alphabet, and let $\Sigma' = \{x' : x \in \Sigma\}$ be a second copy of the alphabet. Define two homomorphisms $h$...
Accepted

### If $L_1L_2$ is regular language then is $L_2L_1$ regular too?

No, $L_2L_1$ is not necessarily regular. Let $L_1 = \{0,1\}^*$, which is regular, and $L_2 = \{1\} \cup \{0^n1^n\mid n\geq 1\}$, which is not. Then $L_1L_2$ is the set of all strings ending with&...
Accepted

### Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages?

The claim "If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third." is not accurate. I'm not sure ...
Accepted

### Why do we study closure properties of formal languages?

I think that the more fundamental question here is why study specific kinds of formal languages at all. One answer is that formal languages of specific kinds have been found useful in the construction ...
Accepted

### Should two DFAs be complete before making an intersection of them?

By definition, a deterministic finite-state automaton $(Q,\Sigma,\delta,q_0,F)$ must have a total transition function: For every $q \in Q$ and $a \in \Sigma$, $\delta(q,a)$ must be defined. Automaton ...

### Is the union between a regular language and a random language also a regular language?

The empty language is certainly regular. Take its union with any non-regular language $N$. What's the result?
The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.) ...
### Prove that regular languages and context-free languages aren't closed under $Perm(L)$
Hints: For regular languages, consider $Perm((01)^*) \cap 0^* 1^*$. For context-free languages, consider $Perm(0^n 1^n 2^m 3^m) \cap 0^* 2^* 1^* 3^*$.