Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,671
questions
-1
votes
1
answer
30
views
Lexical analysis on a series of tokens given regexes
I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct.
...
CommunityBot
- 1
1
vote
1
answer
86
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 ...
CommunityBot
- 1
-1
votes
0
answers
29
views
Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?
When you are deriving a string using a context-free grammar (CFG), you
start with the start symbol and at the right side you have combinations of
variables (non-terminals) and terminal symbols.
Let's ...
- 335
4
votes
3
answers
7k
views
Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:
$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$
My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
0
votes
1
answer
22
views
How to prove correctness of a bidirectional converter between two CF grammars?
I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of ...
CommunityBot
- 1
1
vote
2
answers
1k
views
Prove that $\texttt{prefix}(L)$ is regular
Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular.
So far I have provided that the grammar to produce this language ...
- 1
1
vote
3
answers
133
views
How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?
I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL.
Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$.
When I separate to cases, ...
- 468
2
votes
1
answer
114
views
Formal language rewrite rules: strange notation
I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with.
Here is how "Program=Proof" defines a formal ...
- 11.3k
1
vote
2
answers
83
views
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's.
So far, I have $(aa)^*a((b+\varepsilon)(aa)^*)^4$, but I don't think this ...
1
vote
3
answers
175
views
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
Let $L$ be a regular language.
Define: $half(L)=\{x|xy\in L,|x|=|y|\}$
Prove that $half(L)$ is regular as well.
I have seen a hard proof by using the DFA A of L, building a NFA B (such that every ...
- 27.6k
3
votes
1
answer
80
views
Are the set of all Bitcoin addresses a context-sensitive language?
This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
- 33
1
vote
1
answer
74
views
variable repetitions in pumping lemma for context-free languages
Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz.
The picture below is in support of the proof.
I do not ...
- 34.1k
1
vote
1
answer
67
views
How are regular languages not structurally recursive?
This blog posting states that "regular languages aren't structurally recursive" while
"That's not the case for context-free grammars"
In what sense is the term "structurally ...
- 468
3
votes
4
answers
2k
views
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language?
$\#_a(w)$ is the number of $a$'s in $w$.
So far every language that I saw containing modulo was a ...
- 2,010
-2
votes
1
answer
42
views
Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$
Why is $L'$ a regular language?
I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
- 23.4k
0
votes
0
answers
15
views
Regular, CFL, non-CFL infinite closures [duplicate]
I was wondering about infinite closure properties.
Are the Regular languages closed under infinite union? Infinite intersection?
Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
D.W.♦
- 141k
0
votes
3
answers
130
views
Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$
I have to find a CFG for the given expression:
$L = \{a^wb^xc^yd^z | w + x = y + z\}$
This is what I've tried so far:
S -> aSd | B | ϵ
B -> bBc | ϵ
It works for expressions like: aabcdd, ...
- 25.2k
1
vote
2
answers
53
views
Show that the Hamming distance of $wx$ and $xw$ cannot be 1
Let $w$ and $x$ be two binary strings. Show that the Hamming distance of $wx$ and $xw$ cannot be 1.
I think one approach is a proof by contradiction. I was thinking of explicitly writing out $w = w_1\...
- 3,911
-2
votes
2
answers
113
views
Show that $\{ a^c \mid c \text{ is composite}\}$ is not regular using Dirichlet's theorem
Let $L=\{ a^c \mid c \text{ is composite} \}$. Prove that $L$ is not regular using the pumping lemma. You can use Dirichlet's theorem, which states that if $(a,b) = 1$ then there are infinitely many ...
- 34.1k
1
vote
1
answer
47
views
What would be an easy approach for this Turing machine description?
I am tasked to design a turing machine which calculates the function:
$f(n) = 2n \iff 0 \le n \le 2$, or $4n+2 \iff n>2$
Where "n" is given in binary.
Now, I'm not in the slightest way ...
- 34.1k
0
votes
0
answers
29
views
How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]
I want to show that the language $L=\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL.
If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL ...
- 5,164
0
votes
2
answers
136
views
Is the union of a Turing-recognisable language and a Turing-decidable language Turing decidable? Is it recognisable?
I was studying Turing languages for an exam and I came up with this problem for wich I haven't found a solution online. This is my question:
Let's say we have $L_1, L_2 \subseteq\{0,1\}^*$. $L_1$ is
...
- 34.1k
0
votes
1
answer
57
views
Help with two-tape Turing Machine for $L = \{ a^{n^2} | n \ge 0 \}$ - clarification needed
I came here to ask for help with a two-tape Turing machine for the following language.
$L = \{ a^{n^2} | n \ge 0 \}$
I tried following the advice on this site: Turing machine that accepts L={an2|n≥1}
[...
D.W.♦
- 141k
0
votes
1
answer
48
views
Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
- 27.6k
1
vote
1
answer
122
views
How would I show function $f(x)=4x$ is Turing computable?
How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable?
My guess is obviously there is a finite number of operations ...
- 231
1
vote
1
answer
32
views
Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?
For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\{x2y : |x| = |y|, x\in A, y\...
- 34.1k
1
vote
1
answer
42
views
is there a non-context free language A such that A1 is context free?
Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free?
I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, ...
- 34.1k
2
votes
1
answer
36
views
Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?
Why is this language regular: $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$?
Where $\#_a(w)$ is defined as the number of $a$ in $w$.
Isn't that a concatenation between 2 CFL?
Thanks!
- 468
0
votes
0
answers
37
views
If two states of a DFA are k-equivalent and k+1 equivalent
Let $p,q$ be two states of a DFA, such that $p\equiv_kq$ and $p\equiv_{k+1}q$.
Does it mean that $p\equiv q$ ?
I don't think so, because if the minimization algorithm can continue, they might be ...
- 241
-1
votes
1
answer
65
views
prove $A$ is context-free
Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \{a \in \{0,1\}^* : \text{ no character in an even position is a 0 or no character ...
- 225
1
vote
1
answer
40
views
If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular
Prove/disprove the following claim:
If $L\in RL$ then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$
I think that this is true, and my intuition is by using $L_{pq}$ s.t:
For every $(p,q)\in Q\times Q$...
- 270k
1
vote
1
answer
462
views
Convert ambiguous grammar $S \to 01S1\mid SS\mid\epsilon$ to unambiguous grammar
Given the ambiguous CFG :
$ S \to 01S1\mid SS\mid\epsilon $
I came up with the following CFG which I think is unambiguous:
$S \to 01X \mid 011X$
$X \to 01X1 \mid \epsilon$
Is my CFG unambiguous and ...
- 34.1k
-3
votes
1
answer
90
views
Prove a stronger version of the pumping lemma for context-free languages
Let $L$ be a context-free language. Prove that there exists integer $p>0$ such that
$ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that
$|vwx|\le p$
$|vx|\...
- 34.1k
0
votes
2
answers
339
views
$\{xx^r\mid x\in L_1, x^r\in L_2\}$ is context-free if $L_1$ and $L_2$ are regular languages
I have this problem:
Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language.
I am unsure how to prove that some language is ...
- 34.1k
2
votes
1
answer
64
views
Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free
Let $C$ be a regular language. Prove that the language $D = \{x x^R : x\in C\}$ is context-free.
It's clearly important that $C$ is regular; if the hypothesis were weakened to C being context-free, ...
- 34.1k
-1
votes
1
answer
72
views
Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA
To those of you who saw my post from an hour ago - I deleted it because I came up with an idea.
To summarize, I have to design a PDA for this language, without using the usual method of firstly ...
- 468
2
votes
1
answer
49
views
prove that context free languages are closed under the $\circ$ operation
Prove that if $C$ and $D$ are context-free languages, then so is $C\circ D := \cup_{n\ge 0} C^n D C^n $.
I know that $\{0^n 1 0^n : n\ge 0\}$ is context free, being the intersection of $L(0^* 10^*)$ ...
- 27.6k
2
votes
1
answer
142
views
Why 2- way DFA is equivalent to NFA (and thus DFA)?
We know that A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA)is class of models of computability that behave like a standard Turing machine and can move in both ...
- 27.6k
1
vote
0
answers
16
views
an NFA whose corresponding DFA has at least $2^n - \alpha$ reachable states [duplicate]
Is there an NFA with n states so that the DFA resulting from the standard conversion of the NFA to a DFA has at least $2^n - \alpha$ reachable states for some integer $\alpha \ge 1$?
Let $N= (Q, \...
- 225
49
votes
1
answer
21k
views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
- 122
0
votes
1
answer
45
views
Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $
$L = \{a^nb^m | n \le m \le 3n \} $
This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each ...
- 468
0
votes
1
answer
58
views
Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$
Could someone please help me check if my automaton is correctly designed?
$$L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$$
This was an exercise from our workbook, but their solution is a ...
- 468
1
vote
1
answer
40
views
Is the given language regular, CFL or in P
someone sent me a question lately and I wasn't able to solve it so I'm asking for help.
Question: Given the language
$$L=\{w\in\{0,1\}^*:|w| \text{ is even and the first half of it has a balanced ...
- 270k
0
votes
1
answer
43
views
Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$
I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. ...
- 27.6k
0
votes
2
answers
816
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-...
CommunityBot
- 1
0
votes
0
answers
100
views
Prove that neither given language nor its complement is recursively enumerable
Let $L = \{\langle M, n\rangle \mid\,\, n \geq 5000$ and $M$ is Turing machine that halts for every input and leaves at least $n$ non-blank symbols on the tape when stopping $\}$.
I believe neither ...
0
votes
2
answers
74
views
Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones
$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones
Here is one solution for the productions:
$S \to A1A1A1A$
$A \to 1A | 0A | \epsilon$
However, now I have a question. Could I modify the ...
- 468
0
votes
1
answer
85
views
Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ [duplicate]
I need to find the production rules for the following language:
$L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$
Well, the first thing I could come up with is
$S \to aSb | \epsilon$
But this only covers ...
- 468
1
vote
2
answers
11k
views
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
i am trying to find a cfg for this cfl
L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$
is there a way to count the number of 0's or 1's in the string?
- 34.1k
0
votes
1
answer
17
views
How to prove that a subset of a language L is related to NP while L is related to P?
a friend sent me a question where we're given language $L$ and its subset $E(L)$ such that:
$$E(L)=\{E(w)\ |\ w\in L\}\\\text{such that}\\
E(w)=\{w_{even}=\sigma_2\sigma_4\dots\ |\ w=\sigma_1\sigma_2\...
- 23.4k