Stack Exchange Network

Stack Exchange network consists of 174 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
2answers
56 views

How to prove certain parts of one regular language restricted by another regular language is also regular?

I’ve encountered the following difficult question that I don’t know how to solve. $L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \...
1
vote
1answer
31 views

Fitting a regular grammar to strings from a PCFG: how big does it get?

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$. For finite $n$, it is always possible to find a regular ...
0
votes
2answers
42 views

What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
0
votes
0answers
25 views

Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]

I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
0
votes
2answers
48 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
3
votes
1answer
78 views

Does every infinite context free language contain an infinite regular subset?

Can someone explain to me if this is true or not?
0
votes
1answer
15 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
52 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 ...
1
vote
1answer
24 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 ...
2
votes
1answer
36 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
25 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
64 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
1answer
33 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
89 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
74 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?
1
vote
1answer
53 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
17 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
29 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
38 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. ...
1
vote
1answer
136 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
38 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
54 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
15 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
60 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
40 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
60 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
75 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
56 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
63 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
44 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
52 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
26 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
35 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
19 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
45 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
113 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
88 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
3answers
100 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
72 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
56 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
130 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
47 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
129 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
1answer
59 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
33 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 ...
3
votes
1answer
75 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...
1
vote
1answer
38 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
150 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)$...