Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,392
questions
1
vote
2answers
11 views
PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a ...
0
votes
0answers
21 views
Regular expressions accepted by programming languages but are not regular [duplicate]
The below definition of Regular Language is given in Wikipedia.
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language ...
1
vote
1answer
18 views
A regular language derived from another
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
30 views
Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
58 views
How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can ...
1
vote
1answer
21 views
Regularity of a language constructed from a know regular language
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\...
0
votes
2answers
79 views
How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?
I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.
If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
0
votes
1answer
35 views
How to apply Arden's theory to determine a regular expression
If $P=ab$ and $Q=a^*$,
how do I use Arden's theorem to determine the regular expression $R$.
I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
1
vote
1answer
25 views
Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states
Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is ...
0
votes
2answers
40 views
Can a regular expression be any string from the language described by it? [closed]
Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
1
vote
2answers
44 views
Proving non-regularity via syntactic congruence classes?
Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation:
$$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$
One ...
3
votes
0answers
34 views
BNF rule to regular expression
I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression.
(With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
1
vote
1answer
37 views
Check if a NFA accepts a string of non-prime length
Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.
My ...
0
votes
0answers
29 views
Constant single match regex
I am looking for the name (definition?) of X in:
A regular expression is X iff it has exactly one possible match.
Examples: <empty regex>, abc, ...
0
votes
1answer
49 views
How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma
Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value?
Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one ...
3
votes
1answer
50 views
Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1
A generalized regular expression is like a regular expression but with one more operation allowed: complementation. The (generalized) star-height of a generalized regular expression is the maximal ...
0
votes
1answer
51 views
What language does this deterministic finite automaton accept?
Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
3
votes
2answers
107 views
Proof that L^2 is regular => L is regular
I'm trying to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ with $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right.
I first tryed to show $L \in \...
0
votes
0answers
15 views
Empty LBA why all the configurations must be all equal
While trying to prove the Empty LBA one of the rules says that for having a computational story you have the 3 rules : and one of the 3 rules says that Ci has to produce Ci+1 and all the ...
4
votes
1answer
157 views
Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular
I try to show that this language is regular:
$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$
If I build a NFA and run on it every substring of w (skip other letters ...
0
votes
1answer
77 views
Algorithmic problem of regular, context-free, and recursively enumerable languages
Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free.
Are the following problems algorithmically decidable?
Is $L_1 \cap L_2 = L_3$?
Is $L_1 \...
0
votes
0answers
38 views
Is this grammar in Backus–Naur form?
I'm a newbie and a paper I'm reading specifies the following grammar:
...
0
votes
1answer
77 views
building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }
$\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$
I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ ...
1
vote
1answer
25 views
Prove that the language is not regular through Myhill-Nerode Equivalence
The language is given by: $$L=\{a^nb^m|n<m\}$$
I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence.
Any help ...
1
vote
0answers
52 views
Is every language described by a grammar?
I read the following argument showing that not every language is described by a grammar:
For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
0
votes
2answers
62 views
Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular
Prove that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular.
Here is my try, I would really appreciate if someone could tell me if this is a correct proof.
Proof:
Lets assume L is regular. Then we ...
1
vote
0answers
53 views
Number of words of length n for special language
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
1
vote
2answers
61 views
Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?
For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
3
votes
1answer
97 views
If $A$ is context-free then $A^*$ is regular
I am currently studying for my exam and I am having trouble to solve this question:
Right or wrong: If $A$ is context-free then $A^*$ is regular.
I think it's wrong because if $A$ is context-free it ...
0
votes
2answers
69 views
Is checking if regular languages are equivalent decidable? [duplicate]
Is this problem algorithmically decidable?
L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2?
I think that it is decidable because you can write regular expressions for each ...
0
votes
2answers
39 views
Build PDA for a language with unknown input alphabet
$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows:
$L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$
In this exersice I am not given any ...
5
votes
0answers
80 views
Growth function for non-regular languages
For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence ...
0
votes
0answers
24 views
Proof that truncation of a regular language is regular [duplicate]
Let $L_1$ be a regular language and $L_2$ any language. I want to prove that the language of $L_1$ truncated by $L_2$ is a regular language, i.e.
$$\{w| wx\in L_1 \text{ and } x\in L_2\}$$
is ...
1
vote
1answer
35 views
DFAs are regular languages, but regular languages are closed under concatenation
I have course notes which claim the following two facts:
First, DFAs recognize exactly the regular languages.
Second, regular languages are closed under union, concatenation, and *.
Now I have as an ...
0
votes
1answer
95 views
CFG-Infinite recursion
As you see, the string production process never ends.
Can someone explain me if this language is regular or not ?
$ S \to Α Β S $
$ A \to S $
$ B \to a B b $
-3
votes
1answer
56 views
Myhill-Nerode to prove a language is non-regular
L = {a^n b^2n c^3n | n∈N^+}
I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.
1
vote
1answer
39 views
CFG that generates $1^*$ is decidable
I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this:
$1^* \cap G$ is context free since it is the intersection of a regular ...
2
votes
1answer
39 views
Pumping Lemma,regular languages
Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should follow to prove
that the language is not regular?
Assume that the language is ...
0
votes
1answer
32 views
validation of a pumping lemma proof for regular languages
I have the following regular expression:
Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
32 views
Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma
I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying ...
0
votes
1answer
22 views
What is Pumping length for Union of Regular languages?
This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$
Which one of the following can be a pumping length (the constant ...
0
votes
1answer
79 views
Minimum pumping length of (01)* [duplicate]
Michael Sipser offers the definition:
The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p ...
0
votes
1answer
50 views
Is this language with prefix regular?
Is this language regular?
${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$}
I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|&...
2
votes
2answers
56 views
Prove that every regular subset of $a^nb^n$ is finite
How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?
I know that every finite language is regular, and it's not true that every regular language is finite.
I also know that $...
2
votes
3answers
1k views
Prove or Disprove: an infinite intersection of regular languages is a context-free language
Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$.
Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language.
I ...
2
votes
0answers
28 views
Regular string relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := ...
1
vote
2answers
41 views
Regular of language of all words of length 3
Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$
I think the above language is regular. A DFA can be used to determine the above language.
Am I correct? Is the above language regular?...
0
votes
1answer
26 views
Convert the given NFA to DFA
I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.
First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get
$L\...
1
vote
1answer
34 views
Number of equivalence classes
Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$?
And for the private case that $L$ is regular, ...
1
vote
1answer
32 views
Why Right-Division of regular language with RE\E language is regualr?
I think I can't understand the meaning of language being decidable.
The next case makes no sense to me:
Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
