Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
28