New answers tagged

0 votes

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 ...
user avatar
  • 143k
2 votes

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) ...
user avatar
  • 143k
4 votes
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 ...
user avatar
  • 34.9k
0 votes
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 ...
user avatar
  • 34.9k
2 votes
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 ...
user avatar
  • 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 ...
user avatar
  • 27.7k
4 votes

What are the languages produced by context free-grammars with backspace?

The language of a finite alphabet matched with backspaces is a Dyck language (i.e. it's equivalent to balanced parenthetic expressions); one grammar for it has the productions $L\to a_iL \text{<...
user avatar
  • 11.3k
2 votes

Proving grammar equivalence in simple grammar (generate any sequence of three characters)

You can prove grammar equivalence by showing that they represent the same language,use fixed pont iteration method to find language of context free grammar.
user avatar

Top 50 recent answers are included