2022 Developer Survey is open! Take survey.

Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
-3 votes
0 answers
34 views

The Language of All Palindromes - Is it CFL?

Regarding $L=\{ww^R~|~w\in\Sigma^*\}$ - The language of all palindromes. Is it a CFL? I think it is, because if we take any $\Sigma$, for example $\Sigma=\{a,b\}$, then it certainty is. CFL are closed ...
user avatar
2 votes
1 answer
37 views

Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

I want to construct a context-free grammar for this language: \begin{align*} L = \{uc^nd^nv\mid \ u,v \in \{a,b\}^* \text{ and the number of a's and b's in } uv \text{ are equal}\} \end{align*} I know ...
user avatar
3 votes
0 answers
31 views

Is there an alternative for the formal language theory that could be used for flowchart diagrams?

I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
user avatar
1 vote
1 answer
87 views

Language of Turing machines that go through some configuration infinitely many times on empty input

I've been going through some questions on old homework. Here was a question that confused me somehow. Question: Given a language $$L=\{\langle M\rangle\ |\ M \text{ is a Turing machine. } M \text{ ...
user avatar
2 votes
2 answers
64 views

Myhill–Nerode equivalence classes for the language $b^ia^{5j}$

I have to find equivalence classes for different languages based on Myhill-Nerode. I'm struggling a little bit finding these equivalence classes; for example, the language $L=\{b^*a^n\mid n≡0\pmod5\}$ ...
user avatar
0 votes
0 answers
30 views

How to show a language is not recursive, without using reductions?

I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
user avatar
3 votes
2 answers
1k views

Is this language a context-free language or not?

I try to determine if the following statement is true: for any given language $L \subseteq A^*$ if $L$ is a context-free language then $L_1 = \{u^Rv^R \ | \ uv \in L, |u|=|v| \}$ is also a context-...
user avatar
  • 55
1 vote
1 answer
67 views

An exercise that asks for informal description of the language accepted by a specific PDA

This is a problem that I have found from Introduction to automata theory, languages and computation by John Hopcroft and Jeffrey Ullman. PDA P=({q0, q1, q2, q3, f)}, {a, b}, {Z0, A, B}, δ, q0, Z, {f}) ...
user avatar
  • 13
1 vote
0 answers
58 views

Why do PDAs always halt?

Can’t a PDA get stuck in a cycle of blank transitions? Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases. Does the ...
user avatar
  • 161
-2 votes
2 answers
82 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 ...
user avatar
1 vote
1 answer
48 views

Prove $REJECT\leq_mACCEPT$ and vice versa

a friend of mine sent me a question which he can't solve and I didn't succeed to solve it as well. Question: We define two languages: $$ACCEPT=\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\...
user avatar
2 votes
1 answer
36 views

Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode [closed]

Let $L=\{b^ma^n \mid \text{$m$ and $n$ are coprime} \}$. Using Nerode's theorem, prove that $L$ is irregular. From Nerode's theorem I know that $L$ is regular if and only if the number of equivalence ...
user avatar
1 vote
1 answer
56 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 ...
user avatar
  • 11
0 votes
1 answer
83 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 ...
user avatar
  • 121
2 votes
1 answer
51 views

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$ Here is what I have tried: 1. Starting State Read $a$, Write $x$, Move Right, Go To 2 Read $x$, Write $x$, Move Right, Go To 1 Read <...
user avatar
  • 121
13 votes
4 answers
2k views

Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
user avatar
  • 233
2 votes
1 answer
54 views

Prove/find context free grammar is unambiguous for the language $L$

I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \{ w \in \{a,b\}^+; |w|_a = |w|_b \} $$ Essentially: word $w$ contains at least one $a$ and $b$; where ...
user avatar
2 votes
2 answers
512 views

Context free grammar for a language that is a complement of another

Create a context free grammar for L. $$ L=\{a^nb^mc^k | n+m \neq k\} $$ First I tried to create a CNF for a language that accepts strings in which $n+m = k$. I got this: $$ S \rightarrow aAc $$ $$ A \...
user avatar
  • 61
1 vote
1 answer
67 views

Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA

Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*.$ $L_1 \triangleleft L_2 = \{w\in \Sigma^* \mid \exists v\in L_1, vw \in L_2\}$ For clarity, here is python code that shows $L_3 \triangleleft L_4$: <...
user avatar
3 votes
1 answer
74 views

What is the formalism used to describe optional arguments called?

Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example: foo [opt1[opt2...]] req1 req2 [opt3...] ...
user avatar
-1 votes
1 answer
38 views

Question on formal languages, proving equality [duplicate]

I'm new here and im struggling right now on the following task: I have to show that: (L1 ∩ L2) o L3 = L1 o L3 ∩ L2 o L3 L1, L2 and L3 are three languages over the alphabet Σ. o stands for the ...
user avatar
  • 1
3 votes
1 answer
140 views

Proof that a minimal DFA for a finite language has exactly one trap state

Suppose $L$ is a language with a finite number of strings. We know that $L$ is regular. If $M$ is the minimal DFA for $L$, prove that $L$ has exactly one state that we can't exit if we enter it. I ...
user avatar
  • 61
0 votes
1 answer
27 views

If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular

Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular. I think that this one is true, but I am stuck: Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
user avatar
  • 5
1 vote
0 answers
17 views

Prove that $L=\{a^ib^jc^k\ |\ i\neq j,\ i\neq k,\ j\neq k\}$ satisfies the pumping lemma [duplicate]

I've faced this question while I was solving some past homework and I couldn't really figure out how I would solve it. Question: Prove that $L=\{a^ib^jc^k\ |\ i\neq j,\ i\neq k,\ j\neq k\}$ satisfies ...
user avatar
2 votes
0 answers
22 views

Finding a Context Free Grammar for Different No. of a and b AND Different No. of b and c [duplicate]

The question is from my homework: Is the language $\{a^ib^jc^k\mid i,j,k\geq0\land i\neq j \land j \neq p\}$ a context-free language (CFL)? If yes, please provide a context-free grammar for it. I ...
user avatar
0 votes
1 answer
32 views

Finding a context free grammar (CFG) for a non-context free language (CFL) a^n b^n c^n

It is known that the language $\{a^nb^nc^n|n\geq0\}$ is not context-free (we can prove it using the pumping lemma, as shown here: Is $a^n b^n c^n$ context-free?). Yet, this answer claims it has found ...
user avatar
  • 1
0 votes
1 answer
24 views

Automata Regular Language - if $L_1$ and $L_1-L_2$ is regular, than $L_1\cap L_2$ is...?

Given $L_1,L_2$ which can be any regular / non-regular languages. Let $L_1$ and $L_1-L_2$ be regular languages. I want to know if $L_1\cap L_2$ must be regular or not. So, I wrote $L_1-L_2=L_1\cap L_2^...
user avatar
  • 5
-1 votes
1 answer
59 views

If language $P$ is not regular, is $\{ w \in \Sigma ^* : |w| \geq 1000 \}\cup P$ regular necessarily?

Prove or refute. Let $ L = \{ w \in \Sigma ^* :\ |w| \geq 1000 \} $. Let $ P $ be a non-regular language. Then $ L \cup P $ is regular necessarily. I think it is true, but I don't have any idea ...
user avatar
2 votes
1 answer
58 views

How to identify Context-Sensitive Grammar?

Context-Sensitive Grammar is defined as a 4 tuple G = (V, Σ, R, S) where: V is a finite set of elements known as variables. Σ is a finite set of elements known as terminals V ∩ Σ = Null (empty set) S ...
user avatar
  • 25
0 votes
1 answer
50 views

I require assistance in proving this language as not regular

I'm trying to prove that L = {$0^n1^m0^n | m,n >= 1$} in NOT regular but I am struggling with the demostration process. I know the conditions are that: $|y| > 0$; $'y'$ can't be empty $|xy| <...
user avatar
1 vote
2 answers
68 views

Prove that $L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$ is CFL

I've faced a question in my homework, I was able to solve it but not as desired. Question: Given the language $L=\{0^n1^{n+1}\ |\ \exists k\in \mathbb{N} :\ 4n+2=6k \}$, Prove that it's a CFL (Note: ...
user avatar
0 votes
1 answer
22 views

Constructing product automaton with conjunctive conditions

The question was to construct a DFA which accepts the language $$\{ x \in \{0,1\}^* \mid x\text{ starts with a }0\text{ and has at most one }1\}$$ So I first constructed DFA for '$x$ starts with a $0$'...
user avatar
1 vote
1 answer
40 views

Prove/Refute that $L=\{w\$x^R \ |\ x\ is\ a\ substring\ of\ w\}$ is a regular language

I was solving some exercises about CFL from past years' homework and faced this question. Question: Given the language $L=\{w \# x^R \ | \ x\ is\ a\ substring\ of\ w\}$, prove/refute if it's regular ...
user avatar
-1 votes
1 answer
79 views

Context Sensitive Grammar for $x \# x^R \# x$

This language is given. $L = \{\; x \# x^R \# x \mid x\in \{a,b\}^*\;\}$ I have to figure out a context sensitive grammar for it. I've tried several rules already but it's hard to make a copy of the ...
user avatar
1 vote
0 answers
35 views

Does description method matter in Rice’s theorem?

If $\mathcal{p}$ is a nontrivial property of formal languages, then $L_{\mathcal{p}} = \{ \langle M \rangle \mid L(M) \in \mathcal{p} \}$ is undecidable by Rice’s theorem. What if we describe ...
user avatar
3 votes
2 answers
543 views

NFA: How does it function with empty-string moves?

How does the NFA function on $\epsilon$ input if there is only a single $\epsilon$ string in the language? I understand that $L^* = \bigcup_{i=0}^\infty L^i$ where $L^0 = \{()\} = \{\epsilon\}$ and $L$...
user avatar
  • 175
0 votes
0 answers
24 views

Lower bound for $a^kb^k$ in one-tape TM

For the language $ L= \{a^kb^k | k \geq 0 \} $ How can i show there is no one-tape Turing Machine that can decide $L$ in less than $O(n\log n)$ time ?
user avatar
3 votes
1 answer
154 views

Is $a^nb^mc^k$, $n\neq m$ and $m\neq k$ context-free?

Is the language, $a^nb^mc^k$, where $n\not=m$ and $m\not=k $ in CFL or not? When the condition is changed to $n\not=m ~\|~ m\not=k $, it can be shown that the language is the union of 2 CFLs. However ...
user avatar
3 votes
2 answers
156 views

How to build a deterministic finite automaton from a given one with a new definition for automaton language?

I was given a new definition for a language of an automaton. A word is part of the automaton language if and only if the automaton finished on an accepting state and it was in an accepting state at ...
user avatar
1 vote
1 answer
100 views

Context-free grammar for $\{1^i0^j1^k \mid i+2j=k\}$

Suppose $$L=\{1^i0^j1^k\mid i+2j=k\}$$ How can I construct a context-free grammar for $L$? This is homework. Here is my attempt for the case when $L$ is defined with $i+2j=3k$ instead. \begin{align*} ...
user avatar
  • 1
0 votes
0 answers
42 views

Constructing a PDA for the language of words $uv$ such that $2|u| = 3|v|$

Consider the language $\{ w=uv : 2|u|=3|v|, u,v \in \{a,b\}^+ \}$. How to compare the lengths of the words? How to know where is the end of $u$ and the beginning of $v$? What algorithm is used for ...
user avatar
  • 1
0 votes
0 answers
26 views

prove the intersection of a positive closure of a non-regular language and a finite language is a regular language

Given $L$ a non-regular language and $F$ a finite language I need to prove, or disprove, that $L^+ \cap F$ is a regular language. I tried to prove this using induction on the number of words in $L^+ \...
user avatar
1 vote
1 answer
80 views

Prove that there is no $DFA$ with less than $2^n$ states that accepts $L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\sigma(w)=0\}$

I've faced this question in my homework and I couldn't provide elegant proof for it. We're given $\Sigma_n=\{1,\dots,n\}$ and a language: $$L_n =\{w\in\Sigma^*_n\ |\ \exists\sigma\in\Sigma_n\ :\ ⋕_\...
user avatar
0 votes
0 answers
37 views

How to convert a null state transition in nfa to dfa

i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA) I have tried creating the NFA for the regular expression as given in the above image, From the regular ...
user avatar
1 vote
0 answers
21 views

How does checking correctness with Weakest Preconditions work?

We have this example: {true} assume x > 1; y := x * 2; z := x + 2; assert y > z; {true} They then show this: ...
user avatar
  • 1,873
0 votes
3 answers
105 views

NFA where there are two 0s separated by a multiple of 4

I've been following Automata and Formal Languages in my college and I came across this particular exercise. While the solution presented seems correct, I take on Automata Tutor trying this exercise a ...
user avatar
0 votes
1 answer
55 views

How does one prove that DEC does not parameterize DEC?

The $n$th slice of a set $A \subseteq \Sigma^{*}$ is defined as: $$A_n = \{x \in \Sigma^{*}\mid\langle n,x\rangle \in A\}$$ The definition of parameterization is as follows - $C$ parameterizes $D$ (...
user avatar
2 votes
1 answer
132 views

Useless states in a PDA

I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads: 4.22 A useless state in a pushdown automaton is never entered on any input string. Consider the ...
user avatar
  • 123
1 vote
1 answer
32 views

Argument as to why a word does not belong to a language (pumping lemma)

Given the language $D = \{x^n y^n y^m \mid n,m \geq 0\}$, I have applied the pumping lemma with $k>0$, $n=k$ and $m=0$ and found a word $z = x^{k+q} y^k$ with $q>0$ that does not belong to $D$. ...
user avatar
  • 55
1 vote
1 answer
89 views

DFA for $a+b=c$, where $a,b,c$ are input in parallel

I've faced this question in my homework, it's a bonus question so it's harder than I could do now with my current knowledge, so if anyone could help I'll be thankful. We're given $\Sigma=\{0,1\}^3$. ...
user avatar

1
2 3 4 5
53