# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,527 questions
Filter by
Sorted by
Tagged with
48 views

### Is a language recursive? 2 wrong ways of solving

Let's define: $Disagree(M_1,M_2) = \{x|$The result of $M_1$ on $x$ different from the result of $M_2$ on $x\}$ that means: if $M_1$ accept, $M_2$ reject and vice versa $NPA=\{L|\exists M_1,M_2$ ...
39 views

### If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa

If you are given two languages $A$, $B$ and $$A \leq_T B.$$ Is it possible to $\overline{A} \leq_T B$ or $A \leq_T \overline{B}$? Here is my shot. Case 1: $\overline{A} \leq_T B$ This is only possible ...
48 views

### Textbook on formal syntax (and semantics) of programming languages

I'd like to learn about formal syntax of programming languages: how do we describe the syntax of a programming language and how it should be parsed? How do we assign formal semantics to a parsed ...
62 views

### Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$
This is my attempt at a proof: Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$ $L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...