Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
423 views

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?

For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? [Where $w^R$ is the reverse of $w$] My intuition says it is, as for a regular $L$, the languages $L^*$, $\{y: xyz\in L\}$ and $L^R$ are ...
3
votes
1answer
387 views

Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?

So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division. For these operations/operators, we have some properties like commutativity, ...
3
votes
1answer
786 views

Simplifying regular expressions

This is the homework question: $ \{w \in \{a, b, c\}^* : \text{(no symbol occurs twice in succession in w)}\} $ This is my answer: $$\{((abc)^*| (acb)^*| (ab)^* | (ac)^*)^* | (bac)^* | (bca)^* |...
3
votes
2answers
731 views

Showing Regular Languages are closed under removal of rightmost character

"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular." I tried going by closure properties of ...
3
votes
4answers
901 views

Language where every prefix has almost equal a's and b's

Is the following language regular? $$L = \{x \in \{a, b\}^* \mid \text{in every prefix \(w\) of \(x\), } 0 \le |w|_a − |w|_b \le 2\}$$ If so, give a DFA for it with as few states as possible. ...
3
votes
1answer
867 views

Understanding application of Arden's theorem to find regular expression

I learnt Ardens theorem and its usage as follows: Ardens Theorem Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$ does not contain null string, then $R = Q + RP$ has a ...
2
votes
2answers
285 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
2
votes
0answers
10k views

Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this: Let's take some language L which is non regular. Let's assume compliment of L i.e. $(L^...
2
votes
1answer
104 views

Union of infinitely many regular languages [duplicate]

I need to prove or disprove the following statement. If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular. I know that if two languages ...
2
votes
0answers
75 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
2
votes
1answer
1k views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
2
votes
1answer
2k views

Regular expression to show that all strings contain each symbol atleast once

I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so ...
2
votes
2answers
184 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ $...
2
votes
1answer
87 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
2
votes
2answers
191 views

Regular expression for binary words with few zeros

What is the regular expression for the set of binary strings with the property that every $0$ is followed by exactly $m$ times $1$ and every $0$ is preceded by at least $n$ times $1$? $m$ and $n$ ...
2
votes
2answers
138 views

Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

Let $L$ a language over $X = \{a\}$ defined as follow : $$L = \{ a^{n!} \ | \ n \geq 0 \}$$ I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I ...
1
vote
1answer
520 views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...
1
vote
3answers
8k views

DFA for w|w has a length multiple of 2 or 3 [duplicate]

I am trying to create a DFA and a regex for this kind of exercise: $A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine ...
1
vote
1answer
120 views

Are there regular languages between every two non-regular languages?

I have a question regarding regular languages. Given that $L_1$ and $L_2$ are non-regular languages, can a regular language $L$ exist so it is a subset of $L_2$ and $L_1$ subset of $L$? To be more ...
1
vote
1answer
252 views

How to prove that a bounded pushdown automaton is regular?

I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain ...
1
vote
1answer
794 views

Regular expression - every b preceded and followed by an even number of a's

I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s. I think the regular expression should ...
1
vote
1answer
173 views

How to prove $L \cdot L^{*} = L^{+}$

How can one formally prove $L \cdot L^{*} = L^{+}$ It looks obvious to me since with the concatenation you get rid of $\varepsilon$, but I cannot think of a formal proof through induction or ...
1
vote
1answer
1k views

Regular expression for words in a language where each letter appears at least once

What is a regular expression or finite automaton that will accept words in the alphabet $\{a,b,c \}$ where each letter appears at least once? Acceptable words: $ abc, cba, cbcbcba, abbbcaabb$ ...
1
vote
1answer
65 views

Simulating DFA operations on non-regular languages with finite final state set

A language I'm investigating is not regular since the minimal DFA for the language grows depending on input string size. However, while the number of non-final states increases, the final states are ...
1
vote
1answer
427 views

Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes

This is an extension of a previous question asked by a different user earlier: Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying $y'x' = xy$. $y'u'x' = xuy$. $y'v'x' = xvy$. ...
1
vote
2answers
505 views

What are definite languages? How do you formally define them?

I have a question in my homework that deals with the concept of a definite language. The question defines a definite language as follows - "A language L is definite if there is some k(> 0) such that ...
1
vote
1answer
60 views

How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma? $$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
1
vote
2answers
1k views

Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
1
vote
1answer
5k views

Proof that {$a^m b^n$ | m!=n} is not regular [duplicate]

I know that the language $\{a^m b^n | n\neq m\}$ satisfies the pumping lemma, but it's still not regular (I have to count the # of a's and b's). How can I formally prove it?
1
vote
4answers
336 views

Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half ...
1
vote
2answers
632 views

Proving Regularity of Languages that are 1/k of an already known regular language

There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language ...
0
votes
1answer
191 views

Are all functions with constant space complexity in $REG$?

The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?
0
votes
1answer
280 views

Build a regular expression to define a regular language [duplicate]

The language is an infinite set of chains that are defined by the next conditions. Conditions: ...
0
votes
1answer
118 views

Pumping Lemma for regular language [duplicate]

I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as - ...
0
votes
1answer
212 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
0
votes
1answer
72 views

Three languages and how to decide if they are regular [closed]

From following languages which one is regular and why others are not?And what is the regular expression for regular one. $L_1= \{wxwy | x,y,w \in (a+b)^+\}$ $L_2 = \{xwyw | x,y,w \in (a+b)^+\}$ $...
0
votes
2answers
52 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
0
votes
2answers
639 views

Intersection of regular and not regular

$L_1=\{a^n\mid n\ge1\}$ is regular and $L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular. We know that $L_1\cap L_2$ is regular but, here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?
0
votes
0answers
93 views

How to prove for string of triplets that it is a Regular Language? [duplicate]

Let Σ2 = {0, 1}, and define Σ = Σ23. Informally, Σ* is the set of triples of the form (a, b, c) where a, b, c are single binary digits. Consider a string s ∈ Σ* : it is a sequence of such triples. ...
0
votes
1answer
760 views

Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗. This is what I ...
0
votes
2answers
277 views

Every state in subset automaton is reachable

I'm currently trying to prove that following NFA $\mathcal{M}_0 = (Q, \Sigma, \delta_0,0,\{0\})$ (see picture below) has an exponentially larger DFA $\mathcal{M}$ accepting the same language. $\...
0
votes
2answers
8k views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
-1
votes
1answer
370 views

Regular expression of a language over {a,b} which does not contain substring bbb [duplicate]

I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.
-1
votes
1answer
262 views

Why is $\Sigma^*$ concatenated with some language regular?

Let $\Sigma=\{a,b\}$. Why is the concatenation of any language with $\Sigma^*$ always regular? I found a problem where $(a+b)^*$concatenated with $a^nb^n$ was regular?
-1
votes
1answer
307 views

Prove a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
-1
votes
1answer
619 views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
-1
votes
1answer
1k views

Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
-2
votes
1answer
200 views

Prove that X/Y/Z is context-free

Given languages X, Y and Z, each with alphabet, define X/Y/Z as: X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }. Prove that if X is context-...
-2
votes
1answer
87 views

What is the minimal states for the language DFA?

Let the language $$L = \{ w: \text{ for any prefix } u \text{ of } w : \left|\#_o(u) - 2\cdot \#_1(u) \right| \le 2 \}$$ What is the minimal number of states for a DFA, accepting $L$? $4$...
-3
votes
1answer
96 views

Show whether the language with almost as many 0 as 1 in every prefix is regular [closed]

This is the exercise: Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at ...