Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
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 ...
smallfish's user avatar
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 ...
Mark's user avatar
  • 21
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?
osdinuto's user avatar
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 ...
ErroR's user avatar
  • 1,894
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'...
ErroR's user avatar
  • 1,894
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 ...
ErroR's user avatar
  • 1,894
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 ...
Derek Kwon's user avatar
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 ...
Librapulpfiction's user avatar
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 ...
shinichi's user avatar
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 ...
Robert's user avatar
  • 57
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 ...
Robert's user avatar
  • 57
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 ...
Robert's user avatar
  • 57
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: ...
Crow G. F.'s user avatar
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 ...
Knogger's user avatar
  • 710
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^*$ ...
ErroR's user avatar
  • 1,894
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 ...
ErroR's user avatar
  • 1,894
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?
ErroR's user avatar
  • 1,894
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 ...
ErroR's user avatar
  • 1,894
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 ...
pleaseandthankyou's user avatar
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(...
lafinur's user avatar
  • 181
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$, ...
maya cohen's user avatar
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 $ ...
maya cohen's user avatar
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 ...
Sam's user avatar
  • 143
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 $...
NiStack's user avatar
  • 47
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 ...
NiStack's user avatar
  • 47
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 ...
maya cohen's user avatar
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 ...
maya cohen's user avatar
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 ...
maya cohen's user avatar
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 ...
Knogger's user avatar
  • 710
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 ...
Alice Kim's user avatar
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, ...
Rahul Gopinath's user avatar
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 = \{ ...
hedphelym's user avatar
  • 123
1 vote
1 answer
68 views

Proving the set $R$ is finite

Suppose $L$ is a regular language. Let $R\subseteq L$ be a language with maximal size such that for each $x,y\in R$ neither $x$ be a substring of $y$ after removing a substring from $y$ nor $y$ ...
ErroR's user avatar
  • 1,894
0 votes
1 answer
168 views

Alternative to show intersection of two languages is empty

Consider our alphabet set is $\Sigma$. Suppose $L\subseteq\Sigma^*$. I want to show $L \cap L\Sigma^+=\emptyset$ as one of the bellow options: $x,xy\in L\implies y=\lambda$ $x,xy^2\in L\implies y=\...
ErroR's user avatar
  • 1,894
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 \...
Buco's user avatar
  • 11
1 vote
1 answer
45 views

Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
asamsa's user avatar
  • 11
-3 votes
2 answers
57 views

Contradiction via pumping lemma

So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user avatar
0 votes
0 answers
26 views

Lambda Calculus with State

I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
Ziyu Mao's user avatar
0 votes
1 answer
155 views

Is L={0^n 1^n ∣n≥0} context free language?

I looked through many sources which give this as an example for cfl. It also makes sense according to this: But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can ...
Aum Thakkar's user avatar
0 votes
1 answer
68 views

Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
codeing_monkey's user avatar
2 votes
1 answer
21 views

Valid rules in CSG

In the book of Hopcroft-Ullman (the 1979 edition) there is a rule $Da\rightarrow aaD$ in the example of the CSL language $a^{2^i}$. Valid rules in CSG have the form $\alpha A \beta\rightarrow \alpha\...
Ricardo Wehbe's user avatar
-4 votes
1 answer
28 views

Which one is an LL(2) but not an LL(1)

I'm pretty sure b and d are ll2 and not one but not 100% sure. (a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ B → aBb | Ʌ (b) S → aaScc | aaBbc | aBb | ac | Ʌ B → aBb | Ʌ (c) S → aaScc | aaBbc | B | ac |...
Jonah's user avatar
  • 1
1 vote
1 answer
50 views

Is the class of star-free languages just the complement to counter languages within the regular language class?

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. The wikipedia article states: Another way to state Schützenberger's theorem is that star-free languages and ...
Crea Teeth's user avatar
1 vote
2 answers
83 views

Union of non regular and regular language

So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not. Since I found counterexamples for both cases I want to look at more ...
Theorynoob's user avatar
5 votes
1 answer
383 views

Why is Dyck-2 so important for the Chomsky-Schützenberger theorem?

I have read a lot of times, that models that can parse Dyck-2 are of great importance. It appears that Dyck-2 is interchangeably used like Dyck-N. Afaik the Chomsky-Schützenberger representation ...
Crea Teeth's user avatar
0 votes
0 answers
37 views

Language of words concatenated with themselves

Let $L$ be a regular language. Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
user1868607's user avatar
  • 2,194
-1 votes
1 answer
89 views

Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}

I'm currently having trouble coming with context free grammar to describe this language. My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
bipartite's user avatar
0 votes
1 answer
97 views

Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?

So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
Crypton99's user avatar
1 vote
1 answer
81 views

Is (a*b) or (a*b)* star-free?

Here is the proof of a∗ being star-free: $\Sigma* = \bar{\emptyset} $ $ A∗= \overline{Σ∗(Σ∖A)Σ∗} $ Would this be a proof for $a * b$? : $ A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)} $ For $(A * B )*$ it seems more ...
Crea Teeth's user avatar
0 votes
1 answer
76 views

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
empty-search's user avatar

1
2 3 4 5
57