Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
62 views

Why equality is decidable for regular language but not for $CFL?$

There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. ...
0
votes
1answer
46 views

Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]

We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
144 views

Adding a finite set to a non-regular language

Suppose $A = \{0^{n}1^{n} \mid n \ge0\}$, which is not regular, and let $B$ be a finite subset of $\Sigma^* \setminus A$. Is $A \cup B$ regular?
1
vote
1answer
52 views

Difference between (0)* and (0*)*

I know that, 0* generates, NULL, 0, 00, 000, 0000, ... and so on. But how does (0*)* ...
1
vote
3answers
383 views

Is the set of strings with equal number of 010’s and 101’s regular?

Consider the language $$L = \{ w\in \{ 0, 1\}^*: \#_{010}(w) = \#_{101}(w) \}$$ Is $L$ is regular? If it is not regular, can we prove that using the pumping lemma (only with pumping down)?
-1
votes
2answers
406 views

Uniqueness of solution in Arden's theorem

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below. My question is: What is the logical reasoning to prove ...
4
votes
2answers
74 views

Is the language "substrings of a regular language that are over half the length of the superstring" regular?

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular? I was provided the ...
0
votes
2answers
82 views

What does this language notation specify?

I am given this exercise: Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2. w1=ε w2=aabbcc w3=abbccw w4=aabbcccc w5=...
1
vote
1answer
23 views

Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?

I have a question that says that the complement of a regular language given as: $L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
0
votes
0answers
35 views

Prove that the language such that the concatenation of any string with its complement is accepted by a regular language is regular [duplicate]

I’m trying to solve the following question: Suppose you have a regular language L with the alphabet {0,1}*. Show the language L’ = {x : x x_c \in L} is also regular. x_c is the flipped version of x ...
-1
votes
1answer
39 views

how to prove that a language is regular?

I know that this language is not regular L = {w | na(w) = nb(w)} where na(w) is the number of a's in w. But what if now the language changes to that the number of a's has to be greater than b's? I ...
1
vote
1answer
72 views

I have found an example where regular expression is not closed under concatenation. Where am I wrong?

$a^n$ is a regular expression. $b^n$ is a regular expression. their concatenation is $a^nb^n$ which is not a regular expression.
9
votes
4answers
661 views

If $L_1L_2$ is regular language then is $L_2L_1$ regular too?

We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular too? I try to find a way to prove it... I can't assume of course that $L_1,L_2$ ...
0
votes
1answer
76 views

Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
0
votes
2answers
101 views

Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
0
votes
3answers
155 views

Difference between a regular and a non-regular language

Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then: is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM? is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?
1
vote
2answers
85 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 ...
0
votes
1answer
191 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$ ...
0
votes
1answer
46 views

Simplifying the Language of this DFA

Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
2
votes
1answer
56 views

Implication of the Pumping lemma

I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
1
vote
2answers
74 views

Are regular grammar languages defined from "accepting" states?

In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
3
votes
1answer
103 views

Regular expression vs rational expression

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$. Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows: $|L| ...
1
vote
2answers
63 views

Can a non-deterministic finite automaton die out before reading the entire string?

I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by: However, my problem is: If the ...
2
votes
2answers
64 views

Regular language is closed given transposition of rightmost character to leftmost

It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
0
votes
2answers
83 views

Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma. I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
6
votes
2answers
2k views

Is it possible to build any regular expression in a computer language with just 3 basic operators?

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
0
votes
1answer
54 views

Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
2
votes
2answers
120 views

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
0
votes
1answer
842 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
1
vote
0answers
88 views

Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states

Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
0
votes
0answers
34 views

Is my regular expression correct for this question?

IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
-1
votes
1answer
49 views

High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
4
votes
2answers
2k views

Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?

The language given is $L = \{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$. Is this language regular or not? Since there is no pattern, so it should be non-regular? Kindly help!
0
votes
0answers
58 views

Are the regular expressions equivalent?

Is the following equivalence true? $$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$ I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
1
vote
1answer
85 views

Closure of regular languages under "inverse second half"

Theorem. Show that if $L$ is regular, then so is $$ \varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
2
votes
1answer
184 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
4
votes
2answers
228 views

Why are Regular sets not closed under infinite unions and intersections? [duplicate]

Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a ...
-1
votes
2answers
47 views

Are this languages can be represented by regular expressions?

The set of all words with the same number of 0’s and 1’s. The set of all words contained in {0,1}* that have an even number of 0’s and an odd number of 1’s. I guess first one is NO. Second one seems ...
-1
votes
1answer
50 views

How to determine whether this language is regular?

I've encountered this question recently: Given $\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$ and $n\ge 2$, determine whether the following language is regular or not: $$ L_1=\{w\in\Sigma^*|for \ 1 \...
2
votes
3answers
46 views

If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?

If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular? I think I found a correct proof for this question but my professor says it ...
0
votes
2answers
119 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
2answers
73 views

prove/disprove regularity of languages

Let $L_1 \in REG$ and $L_2 \notin REG$ prove or disprove: $\forall L_1 ,L_2 \text{ } $ $\text{ }L_1^C \cup L_2\in REG \lor L_2\setminus L_1\in REG$ I think that it may be disproved, but I found it ...
-1
votes
2answers
62 views

Is this grammar well-defined? How do I prove the language generated by it is regular?

I have the following problem statement: Is G well-defined here? I am unsure of this since there's no production rule for $X, Y, Z$, and this confuses me a bit. And secondly, how do I prove $L$ is ...
0
votes
1answer
19 views

Complementary language of $L\notin RE,coRE$

I mean if $L'$ defined as $L'=\overline{L}$, when $L\notin RE,coRE$. From the logic point of view it should be $L'\in RE \cup coRE$, isn't? But it's not make sense for me, where am I wrong?
2
votes
2answers
93 views

All words containing at least twice as many zeroes as ones

Consider the language $$ \{ w \in \{0,1\}^* : \#_0(w) \ge \#_1(w) \} $$ consisting of all words over $\{0,1\}$ in which the number of zeroes is at least twice the number of ones. Is this regular, ...
1
vote
1answer
60 views

Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive

I came across the following question: Let $L_1$ be a regular language and $L_2$ be a context-free language. Let $L_1^c$ and $L_2^c$ be their complements respectively. What can be said about $(L_1^c \...
0
votes
1answer
45 views

How to check $L$ is regular or not [duplicate]

If $L=\{w \in \Sigma^*\mid w=uv,\text{ number of occurnce a's in $u$ equal to number of occurrence b's in $v$}\}.$ I think $L=\Sigma^*$ because for any string in $\Sigma^*$, we can split it to $uv$ ...
2
votes
1answer
29 views

Minimal state DFAs for a regular expression of length $n$

I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
4
votes
2answers
168 views

Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
3
votes
1answer
68 views

In what bases is the language $a^n$ regular?

Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular $$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$ I think it's regular ...

1
2
3 4 5
32