Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
-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. ...
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 ...
-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 ...
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 ...
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 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, ...
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 ...
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 ...
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&...
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 ...
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 ...
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 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 ...
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 $\...
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, ...
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\...
-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 ...
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 ...
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 ...
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 ...
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} [...
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 ...
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 ...
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\...
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, ...
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!
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 ...
-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 ...
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$...
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 ...
-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|\...
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 ...
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, ...
-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 ...
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^*)$ ...
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 ...
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, \...
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'...
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 ...
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 ...
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 ...
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. ...
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-...
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 ...
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 ...
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?
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\...

1
2 3 4 5
54