Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
0 votes
2 answers
46 views

Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $a(a+b)^*$ to which i applied pumping lemma. Let the pumping length be $'p'$ and the example string be $$w=a(a+b)^{p-1}$$. The string satisfies the condition that it is at ...
Dhruv's user avatar
  • 3
0 votes
1 answer
27 views

Is $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$ regular

The question asks to determine if any of the following languages above $\Sigma=\left \{ 0,1 \right \}$ is regular. The languages are: $L_1=\left \{ \sigma_1u\sigma_2v\sigma_3:\begin{matrix} \sigma_1,\...
Daniel's user avatar
  • 71
0 votes
1 answer
25 views

Formal regular expression equivalent for this programming regex

Consider these Regexes written in Julia (they should be equivalent in Python): ...
lafinur's user avatar
  • 195
0 votes
0 answers
16 views

Irregular Safety Properties

A regular safety property is a safety property whose bad prefixes form a regular language, https://moves.rwth-aachen.de/wp-content/uploads/WS1920/MC/mc2019_handout_lec4.pdf. My questions is, are there ...
revision's user avatar
1 vote
1 answer
158 views

Why regular languages closed under this operation?

Assume we apply the following operation on the regular language $L$: $$OP(L)=\{a_2a_1a_4a_3\dots a_{2n}a_{2n-1}:a_1a_2a_3\dots a_{2n}\in L\}$$ Why $OP(L)$ remains regular? I think this is as the same ...
ErroR's user avatar
  • 1,942
1 vote
1 answer
49 views

How to prove a function is a bijection (name mangling)?

I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed. We'...
user129393192's user avatar
1 vote
1 answer
64 views

Trying to understand better the solution for $L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$

In this post: For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? @Hendrik Jan have give a really good answer but I'm failing to understand it. I have looked at $L=\left \{ abc \right \}$ in ...
Daniel's user avatar
  • 71
2 votes
1 answer
128 views

Efficiently transforming non-recursive CFG into an NFA

It should be possible to rewrite a non-recursive CFG [1] as an acyclic NFA, since non-recursive CFGs represent finite languages (and thus regular a fortiori). Is there an explicit algorithm to rewrite ...
breandan's user avatar
4 votes
2 answers
120 views

pumping lemma, concatenation of non-regular languages $a \neq b$

Could use some help with the following question. I managed to prove using the pumping lemma that $L_{a \neq b}$, namely amount of a’s not equal to amount of b’s is not regular (using the lemma). But, ...
user169627's user avatar
-1 votes
1 answer
50 views

Regular languages: words from A that do not contain any word from B as a substring [duplicate]

How to prove, by construction and/or regular closures, that if $A$, $B$ are regular then the language $L$ defined by $$L=\{w\mid w\in A,\ \not\exists y\in B\ :\ w=xyz\text{ for some }x,z∈Σ^∗\}$$ is ...
user169627's user avatar
1 vote
1 answer
44 views

Deciding if a regular language is empty can be done in polytime but deciding if it does not accept {0,1}* is not?

In my class we have discussed the fact that, given a representation $\langle R\rangle$ of a regular expression $R$, we can decide whether it accepts any string by first finding an equivalent NFA, and ...
Addem's user avatar
  • 367
0 votes
1 answer
59 views

NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

The question asks to write a NFA for the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \...
Daniel's user avatar
  • 71
0 votes
1 answer
61 views

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

The question asks to write a regex to the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = ...
Daniel's user avatar
  • 71
0 votes
1 answer
41 views

NFA for a regular expression without $\epsilon$-transitions

I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
Acad's user avatar
  • 101
0 votes
0 answers
25 views

How to use Jflex to generate a lexer properly?

I was told that making lexer from scrath is really hard and that we should use built in libraries. I used an already existing example to build my program. It worked but was full of error partially ...
Oh No's user avatar
  • 11
1 vote
1 answer
44 views

Constructing a DFA that accepts the set of binary strings with an even length and an odd number of 1s

For this problem, I decided to tackle it by getting the intersection of the DFA that accepts binary strings of an even length and the DFA that accepts binary strings with an odd number of 1s (as seen ...
picato's user avatar
  • 13
0 votes
0 answers
30 views

Proving that $ \{0^i10^i\mid i\geqslant 1\}$ is non-regular, using only closure results and the fact that $\{a^nb^n\mid n\geqslant 0\}$ is non-regular [duplicate]

I've been thinking about this problem for several hours, but I couldn't complete the proof. here is what I did: suppose $L'$ is regular ($L' = \{0^i 1 2^i\mid i \geqslant 0\}$). we define the ...
Ali's user avatar
  • 1
1 vote
2 answers
69 views

Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
Oh No's user avatar
  • 11
0 votes
1 answer
24 views

Can this Classic Regular Expression be simplified?

I have the following Regular Expression (classic Computer Science definition of Regular Expression, not PCRE or modern computer language RegEx): {(ΣΣ)*00(ΣΣ)*}Σ ∪ Σ{(ΣΣ)*00(ΣΣ)*} It "feels" ...
Diode's user avatar
  • 1
1 vote
0 answers
48 views

A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
Eric_'s user avatar
  • 445
1 vote
1 answer
80 views

Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
cool cat's user avatar
-1 votes
1 answer
69 views

What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
cool cat's user avatar
-3 votes
2 answers
46 views

A more concise Finite Automata for 10 substring?

I am learning about finite automata and trying to create a machine that matches {w ∈ Σ∗| w does not contain the substring 10} I created a DFA where it either starts ...
user168855's user avatar
1 vote
2 answers
68 views

Shortest regular expression possible

The question asks to write the shortest regular expression possible to the following automaton: I see only one way to tackle the problem: Use one of the methods mentioned here How to convert finite ...
Daniel's user avatar
  • 71
0 votes
0 answers
17 views

General rules to tell if a language is regular/CFL/decidable/recognizable

I've been looking online for quite some time for some 'general' rules on this. for example, there's a 'rule' that claims that if a language is like $$L={w\in {a,b,c}^* : count_\alpha (w) =count_\beta (...
Aishgadol's user avatar
  • 355
0 votes
2 answers
100 views

regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them. ...
Daniel's user avatar
  • 71
1 vote
1 answer
64 views

How to show L is non-regular without pumping lemma?

$L=\{(ab)^n : n\text{ is a natural number apart from }6\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?
osdinuto's user avatar
0 votes
2 answers
42 views

NFAs that accept a regular language

Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that ...
Derek Kwon's user avatar
0 votes
2 answers
101 views

how to generate regular expression for the language where symbols have to maintain certain length?

I am having hard time creating regex for languages where symbols must be in certain length. I hope I am not ignorant about rules. we have to generate regex using $^*,|,+ \text{ and }\cdot$ right? I am ...
hxdshell's user avatar
4 votes
3 answers
722 views

Notation in NFA, DFA diagrams and language

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to ...
Derek Kwon's user avatar
0 votes
1 answer
35 views

How to handle odd word

Given the language $L = \{ a^n | \text{n is odd} \}$ I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$. But with odd, I'm ...
Robert's user avatar
  • 57
2 votes
2 answers
368 views

How to handle multiple exponents (Pumping-Lemma)

Example $L = {(ab)^na^k|n\ge k}$ When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I ...
Robert's user avatar
  • 57
1 vote
1 answer
58 views

Does a language dictate the order of the word?

Lets take the Language $$L = \{ (ab)^na^k | n \ge k \}$$ Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium? In simple ...
Robert's user avatar
  • 57
0 votes
1 answer
44 views

Can we say $|xy^iz| = a^{p+i|y|}b^p$?

Using the Pumping-Lemma for $ \{L = a^nb^n | n \in \mathbb{N}\} $. We define $p \in \mathbb{N}$ It exists a word $w = a^pb^p$ For every $|w| \ge p$: $w=xyz$, $y > 0$, $|xy| \le p$ Because of $|...
Robert's user avatar
  • 57
0 votes
1 answer
41 views

How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the Question here it is said that $|xy^2z|<2^{p+1}$ Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
Robert's user avatar
  • 57
2 votes
1 answer
587 views

What does empty string ε actually mean?

I came across this weird expression while learning about regular expressions. $R^+ \cup \varepsilon = R^*$ why does doing union with an empty string makes this regex go from 1 or more to 0 or more?
hxdshell's user avatar
1 vote
1 answer
64 views

Why can't we prove closure under concatenation using DFA?

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
hxdshell's user avatar
0 votes
1 answer
54 views

Is the $L'$ regular or not? [duplicate]

Suppose $L$ is regular and we define $L'=\{x:\exists y\in L \wedge \text{ y be a subsequence of x}\}$. Could we conclude that $L'$ is regular or not? I think it's not regular because if $L=a^*b^*c^*$ ...
ErroR's user avatar
  • 1,942
2 votes
1 answer
41 views

Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular

There is an exercise in a book about finite automata that I couldn't solve: Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
Knogger's user avatar
  • 1,107
1 vote
0 answers
28 views

In regular language inference, how is the observation table kept consistent?

I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
Rahul Gopinath's user avatar
2 votes
3 answers
1k views

Proof that a union of two non-regular languages may be regular

Let $L_1 = \{ a^{n}b^{m} \mid n > m > 0 \} $. Describe a non-regular language $L_2$ such that $L_3 = L_1 \cup L_2$ is regular and $L_3 ≠ A^{*}$ (where $A = \{ a, b \} $) From the trace, I cannot ...
Luca 's user avatar
  • 63
0 votes
1 answer
59 views

Determining the language of a DFA

I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted. the DFA is as such: The ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
69 views

Proving the set $R$ is finite

Suppose $L$ is a regular language. Let $R\subseteq L$ be a language with maximal size such that for each $x,y\in R$ neither $x$ be a substring of $y$ after removing a substring from $y$ nor $y$ ...
ErroR's user avatar
  • 1,942
0 votes
1 answer
64 views

Proving that the intersection of two languages is regular or not?

Let $B$ and $C$ be two languages on $A = \{a,b\}$: $B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$ $C = \{ a^n b^m \mid n,m \ge 0\}$ Describe $B \cap C$ and determine ...
Luca 's user avatar
  • 63
0 votes
1 answer
35 views

If a person accidentally deletes a few letters when they try to type "IDAHO" or "ILLIONOIS", then when is state name unclear or ambiguous?

The Short Version of my Question The following two regular expressions represent two sets of strings. REGEX EXAMPLES OF STRINGS OF TEXT THAT MATCH THE REGEX ...
Toothpick Anemone's user avatar
0 votes
1 answer
67 views

Intersection of a regular and a non-regular language can give a non-regular language?

Determine two languages L and L1 on the alphabet {a,b} with regular L, L∩L1 is non-regular and L1 does not contain L. I came up with this solution: L = { w | w ends with the string aba} L1 = {w | w = ...
Luca 's user avatar
  • 63
0 votes
2 answers
68 views

Can the intersection of 2 non-regular languages ​be a regular and infinite language?

The outline of the exercise is this: Describe two non-regular L1 and L2 languages on A = {a,b} such that L1∩L2 is infinite and regular. The proposed solution to this exercise is: L1 = {a^n b^n | n >...
Luca 's user avatar
  • 63
0 votes
1 answer
42 views

Proving a language is not regular using Pumping Lemma

So I am given the language qr where q is any combination of a's and b's. r is then the reverse of whatever q is. For example, abba is in the language because we can make a q = ab and r = ba I have to ...
CSStudent's user avatar
0 votes
0 answers
40 views

Can someone explain the following NFA?

I'm learning NFA and the following question is confusing me. Can Someone explain the answer. I have a feeling that it might be wrong. Thank you!
ultranoobcoder's user avatar
-3 votes
2 answers
58 views

Contradiction via pumping lemma

So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user avatar

1
2 3 4 5
37