Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,499
questions
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?
