Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
1 vote
3 answers
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
1 answer
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 ...
0 votes
0 answers
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 ...
4 votes
2 answers
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 ...
2 votes
1 answer
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
1 answer
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?
3 votes
1 answer
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 ...
0 votes
0 answers
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 ...
26 votes
1 answer
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 ...
2 votes
2 answers
408 views

Undecidability of minimal PDAs and TM machines

Consider $$L=\{<TM>:TM \text{ is a Turing machine and has minimal states}\}$$ $$L'=\{<PDA>:PDA\text{ is a PDA and has minimal states}\}$$ Which one is recursive? I think neither $L$ nor $L'...
2 votes
1 answer
63 views

Time complexity of specific variant of Turing Machine

Assume a variant of a one-tape deterministic Turing Machine that reads and writes on the portion of the tape that the input $w$ appears (like linear bounded automata). My question is, how we could ...
4 votes
3 answers
684 views

Notation in NFA, DFA diagrams and language

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to ...
1 vote
2 answers
65 views

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Can someone please explain me how to solve this? In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $L$ in such a way that the ...
2 votes
2 answers
357 views

How to handle multiple exponents (Pumping-Lemma)

Example $L = {(ab)^na^k|n\ge k}$ When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I ...
1 vote
1 answer
58 views

Does a language dictate the order of the word?

Lets take the Language $$L = \{ (ab)^na^k | n \ge k \}$$ Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium? In simple ...
0 votes
1 answer
32 views

How to handle odd word

Given the language $L = \{ a^n | \text{n is odd} \}$ I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$. But with odd, I'm ...
0 votes
1 answer
35 views

CFG to CFN conversion

I have questions about how to put the grammar below in CNF - Chomsky Normal Form: S ->aAa | bBb | ВВ; A -> C; B -> S | A; C -> S | ε; I did it like this: I eliminated empty productions: ...
0 votes
1 answer
52 views

Is the $L'$ regular or not? [duplicate]

Suppose $L$ is regular and we define $L'=\{x:\exists y\in L \wedge \text{ y be a subsequence of x}\}$. Could we conclude that $L'$ is regular or not? I think it's not regular because if $L=a^*b^*c^*$ ...
2 votes
1 answer
135 views

The complement of a particular language

We know that Linear context-free languages are not closed under complement, so I encountered a challenge in finding an example to show the above theorem. I think the complement of $L={a^nb^n}$ is not ...
1 vote
1 answer
43 views

Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage

Suppose $L=\{ww^r:w\in\Sigma^*\}$. Already, we know that we can draw a PDA for $L$ such that accept each $w\in L$ with space complexity at least $|w|$. My question is how is it possible to draw a PDA ...
0 votes
1 answer
58 views

How it possible given string belong to given grammar

Consider this context-free grammar: $$G:\\\;\; S\to aSbb|aaSbbb|\lambda$$ Is the string $a^{2020} b^{4020}\in L(G)$? I try to derive such a string but I can't, how it possible?
3 votes
1 answer
309 views

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

I am trying to convert the below context-free grammar into Chomsky Normal Form, specifically, removing rules that have three or more variables or terminators. $$S \to A a B \;\vert\; B b C$$ $$A \to A ...
1 vote
1 answer
66 views

Do there exist infinitely many languages that are RE-complete?

I would like to prove or disporove: there exists infinitely many languagess that are RE-Complete. Here is my attempt of the proof. Let $L$ be any RE-complete language. Define a padded version of $L$, ...
0 votes
0 answers
14 views

Finding program that enumerates a language using Von Neumman's computability paradigm

Given an alphabet $\Sigma$ of $n$ elements, whenever there is some order $\leq$ over the elements of $\Sigma$, we define $s^{\leq} : \Sigma^{*} \mapsto \Sigma^{*}$ as \begin{align*} s^{\leq} \left(...
1 vote
1 answer
52 views

Proof or disproof Fin = Fin-Complete $ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $

$ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $ Proof or disproof Fin = Fin-Complete Where Fin-Complete means that for every $ L_1,L_2 \in Fin $ there exist a valid reduction $ ...
1 vote
1 answer
50 views

Why the Chomsky Hierarchy?

The hierarchy $$\text{regular languages $\subset$ deterministic context-free languages $\subset$ context-free languages $\subset$ context-sensitive languages $\subset$ recursively enumerable ...
2 votes
2 answers
142 views

Prove that there aren't any complete languages

Prove that there isn't a complete language over a given alphabet $\Sigma$. That is, there is no $C \subseteq \Sigma^*$ such that every $L \subseteq \Sigma^*$ is Turing-reducible to $C$. Attempt: Let $...
0 votes
2 answers
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
1 answer
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
2 answers
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 ...
0 votes
2 answers
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-...
0 votes
1 answer
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 ...
0 votes
1 answer
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 ...
4 votes
1 answer
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 ...
2 votes
1 answer
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 ...
0 votes
1 answer
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 ...
0 votes
1 answer
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 ...
2 votes
1 answer
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$ ...
0 votes
0 answers
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
0 answers
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, ...
0 votes
3 answers
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 ...
4 votes
1 answer
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 ...
2 votes
1 answer
58 views

Is the language accepted by a DFA with a fixed word on the stack after consuming it a deterministic context free language?

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 = \{ ...
1 vote
1 answer
119 views

Are there context-free languages whose both intersection and complement of intersection are non-context-free?

It is well known that context-free languages are not closed under intersection or complement. But what about context-free languages $L_1$ and $L_2$, such that $L_1 \cap L_2$ as well as $\left( L_1 \...
4 votes
1 answer
407 views

Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? There is a book here that claims $L$ is not CF (without any elaboration), ...
0 votes
1 answer
277 views

How to design a formal grammar to convert EBNF description to a list of CFG production rules

I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm. Can CFG production rules is generated from an EBNF description by a rewrite ...
0 votes
1 answer
52 views

The language of chains with twice as many $a$s as $b$s is regular?

I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem: Let $L$ be the language of all words that ...
3 votes
2 answers
3k views

Are permutations of context-free languages context-free?

Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
0 votes
1 answer
1k views

Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$

I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$, but how do you verify this? Likewise, how do you verify that this ...
0 votes
1 answer
75 views

Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language

I've been working on this question for a few hours now and I've been trying to figure out the question above. My biggest problem is that I don't know what to do with the $>$ and $\geq$ symbols when ...

1
2 3 4 5
57