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.

1,201 questions
Filter by
Sorted by
Tagged with
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
285 views

819 views

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. ...
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 ...
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.
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. ...
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$, ...
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 '...
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 ...
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 ...
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?
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? ...