# Tag Info

### How can we escape the pipe character in Backus–Naur Normal Form?

I suggest you read up on BNF. For instance, you could start with the Wikipedia article: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form. Often, we put literal characters in quotes, so ...
• 143k

### What role does an asterisk serve in Backus–Naur Normal Form?

I have never seen this syntax before, but most likely, <var-def*> is a typo for (or unusual way of writing) ...
• 143k
Accepted

### Formal grammar of MIU system

As Hendrik Jan remarked, the MIU-rules as a string rewriting system is not a semi-Thue system. Each string rewriting rule in a semi-Thue system does not care about context. A step of rewriting in a ...
• 34.9k
Accepted

### if $RA$ is context-free, is $A$ context-free?

Note that $\Sigma^*A=\Sigma^*$ is a regular language, where $A$ is any language that contains the empty string. So, given language $A$, the existence of an regular language $R$ such that $RA$ is ...
• 34.9k
Accepted

### determining whether a context-free language is regular

As you suspected, $L(G)$ is nonregular. A common strategy to prove a language $X$ is nonregular is to find a regular language $Y$ such that $X\cap Y$ is nonregular. When $X$ is context-free, this ...
• 34.9k
1 vote
Accepted

### prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set

If $AB$ is context-free, so should be the set of all its suffixes. Those include the suffixes of $B$, and if $B$ is complicated enough prefixing $A$ does not change the complexity of the set of ...
• 27.7k