Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
1
vote
2answers
42 views

If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?

I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...
9
votes
2answers
300 views

What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive. So this leads to the question: ...
3
votes
2answers
378 views

If regex describes FSAs, what string formats describe Turing machines?

(Topic summary under the line.) Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
1
vote
1answer
51 views

Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?

The title pretty much explains the question, but still: Is the language $$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$ context-free? I think it isn't and would motivate that suspicion by the following ...
0
votes
1answer
23 views

Poping a symbol on a PDA when Input and Stack are Irrelevant

Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special ...
1
vote
1answer
37 views

Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
-1
votes
1answer
40 views

Context-free grammar for $a^{2n} b^{2n}$

I have just started learning formal languages and here is a question I am facing a little hurdle: Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$. This was what I got at first....
0
votes
1answer
23 views

Question about reduction Proof

I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable. The proof used following idea: Reduce from the $A_{TM}$ problem ...
-2
votes
0answers
34 views

Prove that $ \{w \in \{a\}^* | \nexists n >0: |w| = n^{2}\}$ is not context-free [duplicate]

I've to prove that: $ \{w \in \{a\}^* | \nexists n >0: |w| = n^{2}\}$ is not context-free with the Pumping Lemma. Any clues?
-1
votes
0answers
25 views

How to check whether a language is regular or not? [duplicate]

I am given expressions such as \begin{align} L_2 &= \{ a^n b^{n!} \}, \\ L_3 &= \{ abcva^n \mid v \in \{a,b,c\}^*, n \in \mathbb{N}, n \text{ is even}, |v|=n/2 \}. \end{align}
1
vote
1answer
26 views

Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
3
votes
1answer
47 views

Closure of context-sensitive languages under inverse language substitution

We define language substitution for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L_1(a) L_2(b) L_3(c)$ such that (I guess) ...
1
vote
0answers
30 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...
1
vote
1answer
27 views

How to define the languages of the implicit set system problems?

There are implicit versions of some set system problems or matroid problems. A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets ...
0
votes
1answer
45 views

Describe regular expression

I am learning about regular expression, and trying to describe a regular expression for the language L $\qquad L = \{a^i b^j c^k \mid i+j = k\}$ What is the right approach and how to describe a ...
0
votes
0answers
37 views

Designing CFG that accepts $a^n b^m c^p$ where $n=m+p+2$

I have generated the CFG of $a^n b^m c^p$ where $m = n+p+2$: $S \rightarrow ASC \mid \varepsilon$ $A \rightarrow aAb \mid \varepsilon$ $C \rightarrow bCc \mid \varepsilon$ I have been trying $a^n b^...
0
votes
1answer
30 views

Is a Turing Machine a Well-formed formula?

Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me. But is it ...
0
votes
1answer
15 views

Show that a language with union is not regular by using pumping lemma

Given the language $L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \ \vert w\vert_a \ = \ \vert w\vert_b \} \ \cup \ \{ a,b \}^* }$ I'm really unsure how to even start because of the ...
1
vote
2answers
57 views

How is CLR(1) grammar more powerful than LALR(1) grammar

I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
0
votes
0answers
25 views

Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free [duplicate]

Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma. So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can ...
-2
votes
1answer
47 views

Finding the language generated by this grammar

I'm having problems with this. Can someone help me please. Find the language generated by this grammar over the alphabet $\{0,1\}$: $S\rightarrow BAB\mid CAB$ $BA \rightarrow BC$ $CA \rightarrow AAC$ ...
1
vote
1answer
39 views

Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less. I thought about proving this in two ways: ...
-2
votes
1answer
47 views

CFG for $\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $

$L=\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $ Any help would be appreciated.
1
vote
1answer
31 views

PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

On my compilation theory exam we had the following problem: Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
14
votes
4answers
7k views

Are modern programming languages context-free?

Which language class are today's modern programming languages like Java, JavaScript, and Python in? It appears (?) they are not context-free and not regular languages. Are these programming languages ...
1
vote
0answers
44 views

Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
2
votes
1answer
39 views

Proof that class of languages accepted by DPDA by empty stack is not closed under union

My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property): $$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d :...
0
votes
1answer
30 views

Conditions for an Language to be infinite

given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?
0
votes
0answers
20 views

Algorithmically find a formal grammar for a recursively enumerable formal language

The algorithmic problem is as follows. The input is the source code of a program accepting an integer as input and outputting a finite binary sequence. This program defines a recursively enumerable ...
2
votes
4answers
101 views

Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

I'm trying to prove that the following languague is a regular language: $L=\{ w \mid \lvert w \rvert$ is prime $\}$* What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
1
vote
1answer
34 views

Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $

I'm trying to find a CFG for the following language: $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ What I thought about unsuccessfully is the following: $S \rightarrow SASBS \mid SBSAS \mid \...
1
vote
1answer
21 views

Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular

Given the following language: $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as ...
1
vote
2answers
24 views

Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $

I'm trying to prove the irregularity of the following language: $$L = \{ a^mb^nb^n \mid nm \ge 3 \} $$ I tried to demonstrate that it doesn't verifies the Pumping Lemma but for all words I tried it ...
1
vote
1answer
72 views

What does a non-deterministic guess “look like”?

I have been trying to understand the solution to the following problem: "Show that if $L_2$ and $L_3$ are Turing recognisable, then so is $L_2L_3 = \{w_1w_2 : w_1 \in L_2,w_2\in L_3\}$: which ...
-2
votes
1answer
35 views

Regular expression for binary representation of even numbers?

I need help writing the regular expression over the alphabet (0,1) represent the even numbers in base ten. So basically the regular expression would show represent an even number in binary. (also if ...
1
vote
1answer
28 views

Closure of context-free languages under left-half [duplicate]

The regular languages are known to be closed under the operation "left half": $$ \operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \...
0
votes
1answer
27 views

Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
3
votes
1answer
62 views

Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it. I am sorry but I have ...
1
vote
2answers
51 views

Proving that a language is a CFL

Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string. I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain $y$ as substring}\}$ is a CFL. ...
1
vote
1answer
29 views

Proving Undecidability with reductions - Why do some proofs not use an Oracle?

I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf So as I've learnt it, say we want to prove a new Language L is ...
0
votes
1answer
37 views

Turing decidable languages

On an old worksheet I came across the question If L1 and L2 are two Turing decidable languages, then show that 𝐿1∪𝐿2 and 𝐿1𝑜𝐿2 are Turing decidable languages (high-level description with stages ...
1
vote
0answers
21 views

Prove or disprove that a any language L and its complement have the same amount of equivalence classes [duplicate]

The question is: Given a language $L$ (not necessarily regular), prove or disprove that $Eq(L) = Eq(\overline{L})$. Where $Eq(L)$ is the amount of equivalence classes the language L has, and $\...
0
votes
1answer
35 views

Prove that the following language is not a regular language

Prove that the following language is not a regular language: $L = \{ 0^x1^y | x, y \geq 1\text{ and } x \geq y\vee (x < y \wedge y \mod x = 0)\}$ Is there anyone to prove this ?
1
vote
1answer
38 views

Is the union of infinitely many regular languages always regular? [duplicate]

Prove or disprove or this statement: The union of an infinite number of regular languages is regular. Can someone help?
2
votes
2answers
73 views

Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
0
votes
1answer
42 views

$L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular

Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular.
0
votes
1answer
24 views

Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$

I know that $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\}$ is a context-free language, because I know the context-free grammar, i.e. $$ S \rightarrow AbZ \mid XBc \\ A \rightarrow ...
0
votes
2answers
41 views

Proving that a language defined by a regular expression is equivalent to a right linear grammar

After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me. Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
0
votes
2answers
27 views

Is at least one of L and L complement Turing recognizable

Let the alphabet be {0,1}. Is it true that for every language over this alphabet at least one of L and L_complement is Turing-recognizable
0
votes
1answer
32 views

Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \} $

For the following language, write grammar independent of the text. $$\{a^i b^j: j < 2i \text{ and } j \ne i \} $$ I want a hint to start solving this problem. Where should I start?

1
2 3 4 5
50