Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
-2
votes
1answer
39 views
Is this a regular grammar? What rules make it regular? [on hold]
$\Sigma = \{a,b\}$
$G=\{\{A,B\}, \Sigma, \{A \to BB, B \to aB\mid bB\mid \epsilon\}, A\}$
Is this a regular grammar? Can you justify why is or is not rule by rule?
0
votes
1answer
23 views
Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM
Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. ...
1
vote
1answer
261 views
Language whose intersection with a CFL is always a CFL
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm ...
1
vote
1answer
58 views
Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular
Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.
I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
1
vote
3answers
332 views
Why is this basic language not a regular language?
L = {x in {0,1}* | x has an equal number of 0s & 1s}
Based on the recursive definition of regular languages, isn't it possible to form a single regular language set over the binary alphabet {0,1} ...
3
votes
1answer
69 views
Is the language of words with equal number of 010s and 101s as substrings regular?
Is the language of words containing same number of 101s and 010s regular?
If yes, how can I design a DFA for it?
In general, is the language of words containing equal number of strings which one is "...
6
votes
2answers
1k views
Is there a reasonable and studied concept of reduction between regular languages?
Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?
0
votes
1answer
40 views
Prove that the language is not regular [duplicate]
Prove that the following language $Σ = \{1\}$ is not regular.
$L$ = $\{w | |w| = k$, where $k$ is a prime number}.
How should one go about proving this? Should I use pumping lemma for this?
4
votes
1answer
243 views
Irregularity of language of prefixes of decimal expansion of pi
Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the ...
0
votes
2answers
43 views
Regularity of a language contains more 1's than 0's
The language of all bitstrings with more 1s than 0s, i.e.,
$ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular.
I know I should apply Pumping Lemma and the proof as well, what I cannot ...
1
vote
1answer
22 views
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-1
votes
1answer
33 views
Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?
Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
0
votes
1answer
47 views
Confused about pumping lemma, What i'm missing? [duplicate]
When I apply pumping lemma on this language:
${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular.
let ${n=4}$, then $w=010000$...
0
votes
2answers
46 views
Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma
Showing that the language $L$ with $\{1^n0^m |\space n \neq 2^m\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}...
0
votes
0answers
38 views
construct regular expression for a language [duplicate]
I want a regular expression for the following language.
(a+b+c)*, but does not contain substring "abab".
That means it can be any combination of (a, b, c) except "abab".
I tryed to construct it ...
0
votes
2answers
55 views
Regular grammar with at most one c
I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure ...
3
votes
1answer
65 views
Automaton recognizing ambiguously accepted words of another automaton
Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.
In one of the previous exam, for which no answers are available, it is required to ...
1
vote
2answers
39 views
DFA & RE from descriptive definition of given regular language
I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.
Some strings ...
2
votes
2answers
71 views
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
2
votes
1answer
64 views
Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular?
Prove: $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular.
Is it reasonable to get a DFA with at least 30 states for this language? is there an easier way to prove it is regular?
0
votes
0answers
50 views
Grammar for context free language
I want to give a grammar for the following language:
$$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written ...
2
votes
2answers
48 views
Is there a way a proving a language regular/non-regular that works for every possible language?
In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-...
1
vote
1answer
46 views
Why language is not regular
Taken from site "Geeks For Geeks".
The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language."
example: $\left \{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \...
0
votes
1answer
39 views
Question regarding languages and P
According to this Wikipedia article on unary language every unary language has a binary variant. My question is that given a unary language is there an equivalent binary language in P that is P-...
1
vote
2answers
41 views
Pumping lemma for regular languages
I have a vey specific question regarding the pumping lemma in the context of regular languages. The theorem states that if $L$ is a regular language, then there exists a constant $n$ such that for ...
1
vote
1answer
45 views
Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?
I've been asked to write a DFA for:
$\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$.
I don't believe this is possible. Can anyone confirm if ...
1
vote
1answer
70 views
Which word could I use for the Pumping Lemma proof?
I have the language
$ A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\} \operatorname{with} \...
2
votes
2answers
48 views
Union of a regular and a non-regular language
Let's say we have $L_1$ which is a regular language and $L_2$ which is not.
I understand that if $L_1 \cup L_2 = \Sigma^*$ then $L_1 \cup L_2$ is a regular language.
Does that implicitly mean that ...
1
vote
1answer
39 views
Finding the equivalence classes of a language
I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language
$$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$
The best way I've ...
1
vote
1answer
34 views
How can I create a language using set operation to prove a language is not regular?
My goal is to show, that a given language is not a regular one by using the Properties of Regular Languages.
The language is $ A \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c}...
1
vote
1answer
53 views
How does one use the Nerode-Myhill theorem to prove that a language is regular?
Showing that a language is not regular is straight-forward, because all one needs to do is find an infinite set of inputs which has an injective mapping to the set of equivalence classes which compose ...
1
vote
1answer
377 views
Is a particular string regular (e.g is '010') regular?
If the alphabet is $\{0,1\}$, then is the string '010' regular?
I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to ...
1
vote
1answer
46 views
Let u and v be two strings. What about the reverse order of their concatenaited string?
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?
Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
3
votes
2answers
166 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 ...
4
votes
2answers
64 views
Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?
I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
2
votes
1answer
66 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 ...
0
votes
1answer
77 views
Proving the singleton language {x} is regular for all x ∈ Σ*
So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
1
vote
1answer
47 views
Pumping Lemma vs Myhill-Nerode [duplicate]
I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.
Let us take the following as an example:
$$ L = \{ a^n b^n \mid n \ge 0\} $$
...
0
votes
0answers
57 views
Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]
Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved?
Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
1
vote
1answer
35 views
Pumping Lemma on Language with subtracted length
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given
$$ L = \{ a^k b a^{m-...
0
votes
0answers
18 views
How to find equivalence classes for a regular language? [duplicate]
I was wondering if there is a formal approach to find equivalence classes for a regular language.
My guess:
Construct a minimal DFA based on given regular language.
Based on states in DFA, we can ...
0
votes
1answer
27 views
$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
I think this languages is regular. I write regular expression:
$(1 + 2 + 0) ^ {*} (11 + ...
0
votes
1answer
54 views
Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$
In my opinion complement of the L language is
$L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$
I choose to ...
3
votes
2answers
57 views
First half of context-free palindromes
If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise.
Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
0
votes
1answer
62 views
Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither
$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $
Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-...
1
vote
2answers
80 views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
76 views
Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $
I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My ...
0
votes
1answer
144 views
Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's
The following question on the theory of computation is GATE 2019 CS question 24:
For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
3
votes
2answers
32 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 ...
0
votes
2answers
29 views
Is a language that sits between two regular languages also regular?
Suppose that L0, L1, L2 are languages over the same alphabet and that
L0 ⊆ L1 ⊆ L2.
Is it true that if L0 and L2 are regular, then L1 must be regular as well?
...
