Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
0
votes
1answer
11 views
Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$
The language was $L =\{a^n b^{n+1} : n\geq0 \}$.
This is my attempt:
I believed $L$ can also be expressed as:
$L =\{a^n b^{n}b : n\geq0 \}$
This implies that the number of $b$'s is always greater ...
4
votes
1answer
42 views
Does the following operation makes the language regular?
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 ...
1
vote
1answer
20 views
is it possible to know if a language is regular if its equivalence classes are finite?
i have a theoretical questions, and was wondering if you could help me with it so i could understand the material better.
1)suppose we have some language L over $\Sigma$, can we know if L is regular ...
0
votes
0answers
31 views
proving that a language resambled from 2 other regular languages is also regular(complicated)
Let $L_1$ $L_2$ be regular languages over $\Sigma$. how can i prove that the following language is also regular using 1)closure properties 2)multipication automata:
$(i=1,2,3,...n)\sigma_i \in \Sigma$...
2
votes
1answer
33 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
-1
votes
1answer
20 views
Is it possible to create a regular language from an non regular language? (details inside)
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?
say L is irregular, if we add or remove finite number of ...
1
vote
1answer
48 views
Does this context-free grammar generate a regular language?
Does the following set of production rules produce a regular language or not?
$S \to AB \mid b $
$A \to SB$
$B \to AS \mid a$
I have generated following words with above grammar
$b , baa , baaaa , ...
0
votes
0answers
24 views
Context-free grammar for the language $L_a=\{w:w \neq uu, u\in L((a + b)^*)\}$ [duplicate]
To my understanding, $(a + b)^*$ is a regular expression equivalent to the language $\{a, b\}^*$. Thus, $L_a=\{w: w \neq uu, u\in L(\{a, b\}^*)\}$.
I'm trying to simplify the language even further so ...
0
votes
1answer
28 views
Can someone explain the language L = {w: w = uu, u \in La(1*01*)}
I need help understanding the language L above.
These are my understanding:
- w = uu is a concatenation of ...
1
vote
3answers
73 views
Prove a^4n b^m is irregular using puming lemma
My assignment is to prove that the language
$L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language.
My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an ...
1
vote
1answer
44 views
Proving that co-finite languages can be decided in constant time
I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.
If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.
I'm not sure how to proceed from here. Any hints?
0
votes
0answers
35 views
Is this language with fewer b's than twice the number of a's regular?
Is $\{a^{2n}b^m|0\leq m< n\}$ regular? The lecturer said it is not and referred to the pumping lemma but isn't 2 the pumping length?
For every $n>m$ you can choose $u=\epsilon$, $v=aa$, $w$ the ...
1
vote
1answer
49 views
FSA for $(ab)^*(cb^n)^*$ [closed]
How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?
An automaton can easily be drawn for the part $(ab)^*$, but the part $(...
0
votes
0answers
14 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
10
votes
3answers
2k views
Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)
The Problem
There is no easy way to get a permutation with a regex.
Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters.
Regex: Regular ...
0
votes
1answer
26 views
Closure properties between two languages from different grammars
We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular.
What if we have a regular grammar that ...
1
vote
2answers
37 views
Show language not regular
How can I show that $\{a^ib^jc^k|i=0 \lor j=k\}$ is not regular?
I tried applying the pumping lemma but it does seem to have a pumping length of 1?
Alternatively there is the Myhill–Nerode theorem.
...
0
votes
0answers
19 views
Choice of $x,y,z$ when applying the pumping lemma [duplicate]
I want to determine whether
$$L=\big\{0^i \, 1^j \big| \,i,j \geq 1, \, i\neq j \big\}$$
is a regular language or not.
Attempt:
Let's assume that $L$ is regular. Then for $p=5$, the string $s \in ...
0
votes
0answers
26 views
Given a regular language L and only given an NFA that accepts it , is this enough to say that the complement of L is also regular?
"Given a regular language L and only given an NFA that accepts it then L'(the complement) is also regular"
Is this good enough proof to say that the complement is regular?
I keep being told this ...
0
votes
0answers
9 views
Prove that the grammar in Chomsky Normal Form is not Regular [duplicate]
S-> BS|a
B-> CB|b
C-> SC|c
I am stuck with this problem. Can someone please help me to approach this?
1
vote
1answer
55 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
1answer
34 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
1
vote
2answers
52 views
Prove or disprove L is regular
There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $L$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$
$$A \to 0A | \lambda|A1$$
...
-1
votes
1answer
14 views
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
sigma is any alphabet. R is a regular expression.
How can L(RR) even be a subset or equal to L(R)?
1
vote
0answers
58 views
What is the regular expression for the following language?
What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??
0
votes
2answers
39 views
Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages
I'm trying to create a formal algorithm in order to determine whether
two given regular expressions $a$, $a'$ define identical/equal or
unequal languages and if those languages are subsets of each ...
2
votes
1answer
58 views
Is SAT known to be non-context-free or even non-regular?
We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas.
Has something similar been done for SAT?
2
votes
2answers
64 views
Prove regular languages are closed under $f(n) = 2^n$ and $ f(n) = n^2$
Suppose $ R $ is a regular language, let $ f(R) = \{ w | $ $ \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've ...
1
vote
1answer
36 views
The reverse DFA is not working as expected
Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:
And I reversed the DFA according to this answer (designing a DFA and the reverse of ...
-1
votes
2answers
57 views
Several simple propositions about regular languages
(Originally posted on Math-Stackexchange)
https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions
Notation:
$\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet
$\...
0
votes
1answer
30 views
Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular
I'm having issues using the pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{...
1
vote
1answer
39 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
votes
1answer
18 views
Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]
I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
0
votes
1answer
33 views
Can this DFA be converted to a regular expression? [duplicate]
I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
1
vote
1answer
18 views
Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered
I am not well versed in this topic so please pardon any ambiguous notation.
I am trying to describe the language of this grammar in set-theoretic notation.
The Grammar is given by:
$ S \rightarrow ...
1
vote
1answer
33 views
Designing a context free grammar for a language; When to use the empty string
$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$
How can a grammar be created from the language without the use of the empty string. Below is my ...
3
votes
3answers
97 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 ...
1
vote
1answer
71 views
Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma
I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.
Question
Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$...
1
vote
4answers
87 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
votes
1answer
65 views
Can there exist two minimal dfa for same regular language?
As said the answer is pretty simple "no", but that is not what i encountered. Here is the summary : i took a regular language , produced two ways of accepting same language (the ways in my ...
1
vote
1answer
53 views
Find the number of strings in the language $(∅∅^∗ + ∅)$
Consider the language $L = \emptyset\emptyset^∗ + \emptyset$.
How many words does $L$ contain? Zero or one?
Note: $\emptyset^∗ =\{\epsilon\}$.
0
votes
1answer
87 views
If a language has a regular grammar, is it regular?
If L has a regular grammar, is L always a regular language?
A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.
So would ...
1
vote
1answer
35 views
Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$
I'm asked to find all equivalence classes of the language
$$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$
We have the following definition:
$$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \...
2
votes
1answer
105 views
Regularity of language of words containing a square
$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
0
votes
0answers
51 views
Why does removing all copies of a letter preserve regularity?
Let $P(a,L)$ remove every $a$ in $L$, for example
$$ P(a,\{ab,aab,aaab,bba\}) = \{b,bb\}. $$
How to show that if $L$ is a regular language then $P(a, L)$ is also a regular language?
My attempt:
If $...
0
votes
2answers
32 views
How to deal with character set in regular expression?
In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit ...
0
votes
0answers
16 views
Is the set obtained by taking the first quarter of strings from a regular set $L$ regular as well? [duplicate]
That is, let $L'$ be the set consisting of the first quarter (first $\frac{1}{4}^{th})$ of each string whose length is divisible by 4 in a regular set L. I am pretty sure $L'$ is regular, but I am not ...
1
vote
1answer
35 views
Is my pumping lemma proof correct? [duplicate]
Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular
I'd like to check if my proof for this is correct.
Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+...
6
votes
3answers
2k views
Prove that A** = A*, where A is a language over Σ*
Let $\mathcal A$ be an arbitrary language over $\Sigma^*$
Proof.
To prove, $\mathcal A^{**} = \mathcal A^* $
$\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \...
0
votes
2answers
125 views
Non-regular language whose prefix language is regular
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$...
