# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,846 questions
Filter by
Sorted by
Tagged with
1 vote
374 views

### Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

I've been working on proving that this language L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not Context Free. "na(x)" stands for "number of ...
1 vote
663 views

### Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$ where $n,m \ge 0$ I'm very new to this so this example might be a little harder, but ...
34 views

### How to determine class of formal language in Chomsky Hierachy

I recently started learning about the chomsky hierarchy and I am preparing myself for an upcoming exam. Often there are tasks to specify the smallest classification of a given formal language. How ...
199 views

### Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even. When $j$ is ...
37 views

### Express a language containing the words with an odd amount of 0's using the languages $\{0\}$ and $\{1\}$

This is a homework question and after struggling with it for a while, I have decided to ask for help here. The task is to construct a language over the alphabet $\{0,1\}$ consisting of precisely those ...
1 vote
60 views

### How to show L is non-regular without pumping lemma?

$L=\{(ab)^n : n\text{ is a natural number apart from }6\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?
54 views

### Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

This question is kind of a follow-up to a question asked a few days ago. Both of the non-linear complements of linear languages found were also not context free. So the question is this: Is there some ...
40 views

### Why we could run the algorithm on Linear Bounded Automata?

Suppose there is an algorithm $\mathcal{A}$ for the problem $\Pi$ that halts on any instance $x\in\Pi$. Someone tells me that we can run $\mathcal{A}$ on Linear Bounded Automata, but I can't ...
9k views

### How to show that L = L(G)?

Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
408 views

59 views

### Prove the existence of a language L over the alphabet Σ = {1} such that L ∌ RE and L ∌ CoRE

I attempted to create a language $L_1$ = {$<M>| L(M) = 1^*$} and prove using a reduction that $L_1$ ∌ RE and $L_1$ ∌ CoRE by showing that $HP ≤ L_1$ and $\overline{HP}$ $≤ L_1$. But my ...
1 vote
88 views

### Proof or Disproof if $L$ is a Regular language then it has to be that $L\leq HP$

Proof or Disproof if $L$ is a Regular language then it has to be that $L\leq HP$ $HP=\{<M,x> | M \ halts \ on \ x \}$ Regular language is a language that can be expressed with a regular ...
1 vote
100 views

### How to prove $\{\langle M\rangle: L(M)=\emptyset\}$ is undecidable?

Consider the language $$E_{T M}=\{\langle M\rangle: L(M)=\emptyset\}.$$ Prove that $E_{T M} \in \text{coRE} \backslash\text{R}.$ I proved that $$E_{T M} \in\text{coRE}$$ using Turing machine I built ...
930 views

### Turing Machine for $\{w\# w ' |$ where $w < w'$ lexicographically, and $w,w'\in \{0,1\}^* \}$

I am blocked with this question for a long time. $L = \{w\# w ' |$ where $w < w'$ lexicographically, and $w,w'\in \{0,1\}^* \}$ I am trying to find A Deterministic Turing Machine for L. A Non-...
36 views

### proof or disproof if $L_1 \subseteq L_2$ then $L_1 \leq L_2$

proof or disproof if $L_1 \subseteq L_2$ then $L_1 \leq L_2$ I tried to think with HP and the empty language because HP is in RE and the empty language is in R but how do I prove this does not ...
93 views

### Proof or disproove $L_1 , L_2 \in RE \setminus R$ such that $L_1 \cup L_2 \in R$ and $L_1 \cap L_2 \in R$

Proove or Disproove $\exists L_1 , L_2 \in RE \setminus R$ such that $L_1 \cup L_2 \in R$ and $L_1 \cap L_2 \in R$ I tried to use the languages the union is $\sigma^*$ and the ...
8k views

### Is it possible that the union of two undecidable languages is decidable?

I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$. I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't ...
41 views

### Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular

There is an exercise in a book about finite automata that I couldn't solve: Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
38 views

### Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}

Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1} Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
970 views

### Show that an instance of PCP or MPCP has no solutions

I'm studying the Post Correspondence Problem (PCP) and understand the concept, although I have problems with proving how to show that an instance of a PCP or modified PCP has no solutions. For ...
208 views

### Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular

Question : Are my Justifications Correct? Pumping Lemma $A = \{0^n1^n \mid n \geq 0\}$. Prove $A$ is not regular : Suppose $S = 0^p1^p$ and $p = 3$. Therefore, $S = 000111$. Breaking $S$ into $xyz$ ...
42 views

### context-sensitice grammar for a language

I have been stuck on a task in class. I have to find a context-sensitive grammar for the language $L=\{a^{n}b^{2^{n}}|n \in \mathbb{N}\}$ and I just cannot figure it out. Any help would be very much ...
1 vote
28 views

### In regular language inference, how is the observation table kept consistent?

I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
172 views

### Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language

I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
90 views

### Proving that $(A \cup B)^* = A^*(BA^*)^*$

I would like to prove that $(A \cup B)^* = A^*(BA^*)^*$, where * means the Kleene star. I would like to use induction to prove this equality but I do not how to proceed and how is the best way to set ...
Let $\cal M$ be a deterministic stack automaton ${\cal M } = (Q, \Sigma, \Gamma, \delta, q_0, F, Z_0 )$. Let $\gamma \in \Gamma^*$ a word on the stack alphabet. Is it true that the language L = \{ ...