Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,631
questions
-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 ...
- 1
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 ...
- 23
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 ...
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{ ...
- 313
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\}$ ...
- 21
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 ...
- 141
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-...
- 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}) ...
- 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 ...
- 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 ...
- 115
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\...
- 313
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 ...
- 241
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 ...
- 11
0
votes
1
answer
84
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 ...
- 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 <...
- 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. ...
- 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 ...
- 23
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 \...
- 61
1
vote
1
answer
68
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$:
<...
- 163
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...]
...
-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 ...
- 1
3
votes
1
answer
141
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 ...
- 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 ...
- 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 ...
- 313
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 ...
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 ...
- 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^...
- 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 ...
- 115
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 ...
- 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| <...
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: ...
- 313
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$'...
- 105
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 ...
- 313
-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 ...
- 13
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 ...
- 336
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$...
- 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 ?
- 336
3
votes
1
answer
161
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 ...
- 265
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 ...
- 241
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*}
...
- 1
0
votes
0
answers
43
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 ...
- 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^+ \...
- 241
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\ :\ ⋕_\...
- 313
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 ...
- 1
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:
...
- 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 ...
- 11
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$ (...
- 101
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 ...
- 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$.
...
- 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$. ...
- 313