The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
128 views

Show that some context free languages must contain more that one non-terminal

Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular set,...
4
votes
1answer
54 views

Does the following operation makes the language regular? [duplicate]

I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it. However I thought what could happen if the language is ...
4
votes
1answer
231 views

Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression? The way I solved this problem is to first convert the NFA ...
4
votes
1answer
701 views

Using finite state machines for lexical analysis

I'm a high school student and I'm passionate about everything language related - lexers, parsers, compilers, interpreters and so on. Some time ago I've written a calculator in Python (now willing to ...
4
votes
1answer
830 views

Recursive definition of a language given the regular expression

Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$ I know that there is a DFA that accepts this language, and furthermore, that the regular ...
4
votes
1answer
2k views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
4
votes
1answer
206 views

Is the symmetric difference of a non regular language L and a finite language f non regular?

The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$. Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
4
votes
1answer
67 views

Is repetition the origin of countability?

The original question was "Do all non-regular languages have an uncountable number of strings?". How can someone prove that..? I am squeezing my head but I can't figure it out. And the other side ...
4
votes
1answer
285 views

How do I show that an equivalence class of a language containing an empty string is infinite

The question is as follows: Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not $\{ \epsilon \...
4
votes
1answer
474 views

Basic Myhill-Nerode Theorem Practice

I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so. L = (a $+$ b ) Clearly, this language is regular. So, I should be able to establish a finite number of ...
4
votes
2answers
3k views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
4
votes
1answer
191 views

Finding two words of lengths that are relatively prime in a regular language?

Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$. How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?
4
votes
1answer
27 views

Proving a language comprised of 2 languages is regular

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it. The question: $L_1$ and $L_2$ are regular languages over the ...
4
votes
1answer
205 views

How to prove that a transformed language is regular using an NFA

I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $ plus (L) $ consisting of ...
4
votes
1answer
132 views

Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in ...
4
votes
1answer
420 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
3
votes
5answers
3k views

Show that every infinite language has a non-regular subset

I'm trying to solve this problem: Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular But can this be correct? If I have the language $\{a\}^*$ for ...
3
votes
2answers
938 views

Regular language with pumping lemma

I have that language $S=\{a^n b^m c^m\mid n,m \geq 0\}$. How can I prove with the pumping lemma that it isn't regular? Can I use the concatenation closure and say that it's the language $L_1 = \{a^n\...
3
votes
2answers
819 views

If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular. I need some help on getting started on proving this is the case. My intuition is that if $L_1 \...
3
votes
4answers
16k views

Designing a DFA that accepts strings such that nth character from last satisfies condition

This is a homework question, so I am only looking for hints. I got a question in an assignment which states : Design a DFA that accepts strings having 1 as the 4th character from the end, on the ...
3
votes
5answers
41k views

Regular expression for the strings without a particular substring

How can we design a regular expressions without particular substrings. The goal of this is to create language L which won't contain a particular substring (i.e. 110)...
3
votes
2answers
156 views

Is $(aaaaa)^n aa (aaaaa)^n$ a regular language?

Is the language $\lbrace (aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N} \rbrace$ regular? It looks like I need infinitely many states so it is not regular.
3
votes
3answers
107 views

Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?

Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet. Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$? What if $L_1$ and $L_2$ are regular languages? Can you give ...
3
votes
3answers
4k views

How to convert a context free grammar (could generate regular language) to a right-linear grammar

Consider the context free grammar: $$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$ It could generate regular language, which means it can be converted to a right linear grammar. Is ...
3
votes
2answers
3k views

Are regular languages closed under inverse homomorphism?

Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \...
3
votes
4answers
212 views

How to determine if a regular language L* exists

I'm trying to make sense of regular languages, operations on them, and Kleene operations. Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that ...
3
votes
1answer
3k views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
3
votes
3answers
198 views

Decide if L is regular or not and argue it. Trying to use Pumping Lemma

Part (a): Let $L = \{x \in \{0,1\}^* \mid \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$. So I want to use the ...
3
votes
2answers
199 views

Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$

I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$. ...
3
votes
3answers
3k views

If L is regular, show that even(L) is also regular

I am stuck on the following question. If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)...
3
votes
4answers
906 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
3answers
1k views

Metrics and algorithms for complexity of a graph

I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short ...
3
votes
2answers
343 views

Why is the subset of palindromes of a regular language context-free?

Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language? Trying to understand the approach to determining whether a regular language is context-free.
3
votes
1answer
4k views

DFA that accepts decimal representations of a natural number divisible by 43

First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. ...
3
votes
1answer
547 views

Does a regular expression model the empty language if it contains symbols not in the alphabet?

Suppose $\Sigma = \{ a,b \}$ and the regular expression $(a^*b+dc)^*(b^*d + ad)^*$. Is it equal to $\varnothing$? So I have a regular expression like this: $(a^*b+dc)^*$. As only $(a,b) \in \Sigma$, ...
3
votes
3answers
390 views

Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the '...
3
votes
2answers
1k views

Why is every finite language A ⊆ Σ* regular

So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can ...
3
votes
2answers
53 views

variable exponent in expression of a formal language

Take a look at the following expression: {(AnB)m|n>0,m>0} Or, to put it simply: the words in the language, have repeating parts consisting of, some A's followed by a single B. There are TWO school ...
3
votes
2answers
1k views

Infinite Intersection/Union of regular languages

Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular. Can someone please give me some good examples?
3
votes
4answers
1k views

Why does this Pumping Lemma example show irregularity?

the first 4 steps of these are my own work - however the following steps are from my book, and I don't understand what it's saying, and I have not found any resources. Could someone clarify this? ...
3
votes
1answer
102 views

Find a regular language that is “infinitely between” two other regular languages

Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq ...
3
votes
3answers
2k views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
3
votes
3answers
2k views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\...
3
votes
2answers
35 views

What's the true meaning of $(a + b)^\omega$ in regular expression

I'm starting to dabble in language theory, regular expression & infinite words. I'm not quite sure I completely get the meaning of this expression: $(a + b)^\omega$ $^w$ meaning infinite ...
3
votes
1answer
426 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
2answers
737 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
1answer
1k views

Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular? [duplicate]

Suppose we have some regular language $L$, then can we say that $$L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $$ is also regular? I have a 'feeling' that ...
3
votes
3answers
156 views

Is the power of a regular language regular? Is the root of a regular language regular?

If $A$ is a regular set, then: $L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$, $L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$. Which one of them is regular? My reasoning is since ...
3
votes
2answers
126 views

Constructive Proof on Regular Languages

As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages. $$L_1=\{w│w^R∈A\}$$ $$L_2=\{w│w=a_1 b_1,…,...
3
votes
1answer
140 views

Determining if (infinite) binary language DFAs contain at least 1 prime?

This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. [1][2]...