# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,049 questions
Filter by
Sorted by
Tagged with
50 views

I am having trouble solving the following task: Given is the language $$D=\{ \langle M, w \rangle \mid \text{M is a Turing machine and M enters all states on input w}\}$$ Prove that $D$ ...
53 views

### Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language? It certainly isn't regular, but is it context free? I'm having trouble creating ...
88 views

### Finding a regular expression of a language

Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3. Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
39 views

### Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$ [duplicate]

$L_1^*∪L_2^*⊆(L_1∪L_2)^*$ I actually disproved the opposite proposition $[(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true... I tried to show that the combinations of ...
36 views

### What's the difference between ioco, uioco and tioco in Model Based Testing?

I'm learning about formal languages and Label Transition Systems (LTSs) and how to test systems using Model-Based Testing. Specifically, the paper Model Based Testing with Labelled Transition Systems ...
102 views

### Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?

Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet. Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$? What if $L_1$ and $L_2$ are regular languages? Can you give ...
51 views

### Show that the following language is undecidable

$\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\}$ I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first ...
14 views

### building turing machine for busy beaverproblem

I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
65 views

312 views

### Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular. I haven't managed to prove this, but I'm ...
72 views

### Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b \}$ is not regular. I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
50 views

### How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
52 views

### Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
67 views

### how can one counter machine accepts a^n b^n c^n?

It is mentioned in Which languages are recognized by one-counter machines? that one counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?
59 views

### Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$ [closed]

I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar. I need help. Thanks all of you! :)
116 views

### Can a TM recognize whether another TM recognizes a non-empty language?

Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$ Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm? My attempt: I wanted to study ...
23 views

I'm struggling with the following question: Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{... 1answer 87 views ### Finding two languages satisfying conditions Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$ Prove that there are two languages$L_1, L_2$such that$L_1, L_2 $are infinite.$L_1 \cup L_2 = E_{TM}...
The language of all bitstrings with more 1s than 0s, i.e., $A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular. I know I should apply Pumping Lemma and the proof as well, what I cannot ...