Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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? [closed]

$\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?
11
votes
4answers
2k views

Star free language vs. regular language

I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example? (from wikipdia) Lawson defines star-free ...
1
vote
1answer
53 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 ...
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
262 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?
1
vote
1answer
123 views

Show that language is context-free

Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such ...
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
1answer
41 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?
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 ...
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
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*) ?
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.
2
votes
1answer
69 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??
5
votes
1answer
383 views

DFA, lower bound on number of states, language with primes and remainders

This is an exercise from old exam on formal languages that I don't know how to solve: Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i....
5
votes
2answers
378 views

How to prove “if every subset of a set is a CFL, then the set must be regular.”

"If every subset of a set is a CFL, then the set must be regular." I want to prove it, could anyone please give me some hints?
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 ...
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}...
3
votes
4answers
15k 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 ...
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 ...
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 ...
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-...
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
162 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ $...
1
vote
1answer
38 views

Prefix/suffix property of language containing only empty word

Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property? The definition says that language has prefix/suffix property requires that there is no code word in the ...
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 ...
0
votes
1answer
45 views

How can I find the Myhill-Nerode classes for the language A?

I have the following task (no homework). Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$...
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-...
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
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?
6
votes
1answer
1k views

Why is deciding regularity of a context-free language undecidable?

As I have studied, deciding regularity of context-free languages is undecidable. However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient ...
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} \...
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} \...
1
vote
1answer
258 views

Tokenization Problem

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult. My Regular ...
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 ...
2
votes
1answer
54 views

How to choose a word to apply the Pumping Lemma?

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :) ...
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
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
54 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 ...
0
votes
1answer
69 views

picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}

If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$ when i pick a word for the language, would it be correct if i pick any of these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^...
3
votes
1answer
9k views

designing a DFA and the reverse of it

There is a theorem that says if a language is regular, it's reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?
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.
0
votes
1answer
146 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 ...