# Tag Info

Accepted

### Do all instances of a given string get replaced under a rewrite rule?

Probably your course teaches the context-free grammar. Indeed, in a CFG one position in the string is chosen, and the symbol at that position is rewritten using one of the rewrite rules. In a CFG the ...
• 30.9k
Accepted

### Give a class of languages which is closed under intersection and union, but not under complement

An example of a class of languages which is closed under union and intersection, but not under complement is the class of finite languages. Context-free languages are closed under union, but not under ...
• 30.9k
1 vote

### Detect (indirect) left-recursion in a context-free grammar?

You can solve that by modelling the recursions. Make a graph, where $A$ points to the beginning symbols of the $\alpha$'s. Etcetera. Then detect cycles in that graph. I have no clue whether the ...
• 30.9k
1 vote

### Do all instances of a given string get replaced under a rewrite rule?

Rewriting systems usually apply each rule once, sequentially. The left hand side might match at several points, in which case any match could be taken,
• 14.1k
1 vote

### Proving that two languages both represent valid bracket sequences

Prove by induction that if $w\in L_2$ then $0w1 \in L_2$. Case $w = 01$, we want to prove $0w1 \in L_2$. Indeed, we start with $01 \in L_2$, and then use the second rule with $w_1 = 0$, $w_2 = 1$. ...
• 685

Only top scored, non community-wiki answers of a minimum length are eligible