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-language]

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

2
votes
1answer
30 views

regular language equality prove by induction

let $L\subseteq\{0,1\}^*$ be declared by the following conditions: a. $0, 01\in L$. b. if $w_1,w_2\in L$ so $w_1\cdot w_2\in L$. c. if $w\cdot 0\in L$ so $w \in L$. prove that $L=\{w| w=\epsilon\: ...
0
votes
0answers
7 views

Prove that a CFG expresses all the strings expressed by the language L

How can I prove that the CFG: S → A | B A → ɛ | 0A0 | B B → ɛ | 1B0 Expresses all the strings from $L = \{0^m1^n0^{m+n} \mid m, n \geqslant 0\}$? (I'm sure this is simple but for some reason I ...
1
vote
1answer
32 views

How can I prove given language is not regular?

My first post here, so glad I found this great place. Hoping I could improve and learn a lot from you and contribute in the future if I can. I have a problem with the following scenario: Given $\...
0
votes
1answer
16 views

Identify the Nature of the given Language

If I am true then following two languages are not equal:- $L_1 = \{(a^nb^m)^l / n,m,l \geq 1 \}$ $L_2 = \{(a^*b^*)^*\}$ And I think $L_1$ is not $CFL$, because suppose a case where I put $n=2$, $m =...
0
votes
1answer
31 views

Left Linear Grammer to Right Linear Grammer

I am learning Regular Grammar and given the problem to convert S->S10/0 from left linear to right linear grammar. I've seen examples of such conversions where we first write the reverse ...
0
votes
1answer
15 views

Prove using the Pumping Lemma

Can I prove that the language of the palindromes in the alphabet consisting of the ASCII symbols is not regular by proving that L = {$1^n21^n$ | n⩾0} is not a regular language?
-1
votes
0answers
40 views

Language of prefixes of regular language is regular language

Let there be L which is a regular language and let there be M which is a Finite Automaton for it. How is it possible to prove that a language L2 containing all prefixes of the L language is a regular ...
0
votes
1answer
7 views

How to prove that $L=\{w\in\{0,1,2\}^*|\#_2(w)<\#_0(w)\}$ is not regular using Myhill–Nerode theorem?

How to prove that $L=\{w\in\{0,1,2\}^*|\#_2(w)<\#_0(w)\}$ is not regular using Myhill–Nerode theorem? $\#_2(w)$ means the number of occurrences of $2$ in $w$, same goes for $\#_0(w)$. I thought ...
2
votes
1answer
64 views

Is there a metric with wildcard?

Is it possible to define a metric over a set of elements $e=(x,y)$ where $x,y\in \{*,0,1\}$, $*$ being the wildcard symbol? For simplicity, assume all words of length 2, i.e. $0*$, $11$ and $**$. ...
1
vote
1answer
18 views

Show that the following language is context-free/not context free by expressing the language as the union of three other languages.

I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$...
1
vote
1answer
32 views

'$L$ almost' is regular

Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char. for example, if $L = \{aab,aaa\}$, so $...
1
vote
1answer
26 views

$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$. x is palindrome of length n. Find regex for $n = 1$

$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n where $\Sigma = \{0,1\}$ I'm having a hard time understanding this ...
0
votes
1answer
12 views

How to determine the beginning of $uv^iw$ in the pumping lemma for regular languages?

Let $\sum=\{a,b,c,d\}$, $L=\{a^ib^jcd^k \big| i\ge0; k>j>0\}$. Prove that $L$ is not regular using pumping lemma. We can choose the word $Z=a^0b^{n}cd^{n+1}=b^{n}cd^{n+1}\in L$. Let $uvw$ be ...
0
votes
0answers
28 views

How to prove that if $L$ is a regular language then $L'$ which is composed of words in $L$ with substrings as also words in $L$ is regular as well?

Let $L$ be a regular language. Let $L'=\{\sigma_1...\sigma_n|n\ge 1, \forall 1\le i\le n, \sigma \in \sum. \exists i: 1\le i\le n \quad\land\quad \exists u\in L: \sigma_1...\sigma_{i-1}u\sigma_{...
0
votes
1answer
21 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)?
2
votes
0answers
38 views

prove that your language is not regular by using the Pumping Lemma, $L = \{x \in \{0, 1\}^* | x = x^R \}$

prove that your language is not regular by using the Pumping Lemma, $L = \{x \in \{0, 1\}^* | x = x^R \}$ proof: Let $L = \{x \in \{0, 1\}^* | x = x^R \}$ Suppose L is a regular language let $x = ...
0
votes
1answer
19 views

Drawing a dfsa where L is a set of strings that contains at most 4 zeros

For each of the following languages over alphabet $Σ = \{0, 1\}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are ...
1
vote
1answer
40 views

If RS is equivalent to SR, then R*S* is equivalent to S*R* (Proof by Contradiction)

R and S are arbitrary regular expressions. I need a counter example where this is not true. I am unable to figure this out.
0
votes
1answer
34 views

Inductive Proof With Regular Expression

I'm trying to prove that the elements of the language $L((01+10)(01+10)^*)$ have an equal number of $0$'s and $1$'s. So far I've the base case: $R^n \to R^0 = 01 + 10$, all of which have equal number ...
1
vote
1answer
30 views

How to use product automaton and intermediate state to prove existence of regular language?

Let $L$ be a regular language over alphabet $\Sigma$. Let $\frac{1}{2}L$ be the following language: $\{w\in\Sigma^* \mid \exists y\in \Sigma^*: |y|=|w|, wy\in L \}$. For example if $L=\{\epsilon, ...
1
vote
1answer
24 views

proof that a language is a regular according to another language

let $L\subseteq\Sigma^*$ be a regular language. for $\sigma \in \Sigma$ prove that $L'=\{w_1\sigma w_2:w_1w_2\in L\}$ is a regular languge. I tried induction on the length of the regular expression ...
0
votes
2answers
54 views

Use Pumping Lemma to show that $L_7$ is not context-free

I was studying an old test and struggled to answer this question: Let $L_7$ be the language $\{ w@y \mid y \text{ is a substring of } w\}$, where $w, y \in \{c,d\}^*$. Use the Pumping Lemma for ...
1
vote
1answer
43 views

Proving equality of two regular languages using operations closed under regular languages

Is there any way to prove that two regular languages A and B are equal using only closed operations under regular languages? (The languages can be expressed as regular expressions,NFAs, eNFAs or DFAs)...
0
votes
1answer
41 views

Show that $\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language by using pumping lemma

$\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language. I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, ...
0
votes
1answer
62 views

Prove that Language is not regular using pumping lemma

Let's have this language: $ L= \{ w_1 @ w_2 | w_1,w_2 \in \Sigma^*, \#_1(w_1)+(2*\#_2(w_1))=\#_1(w_2) + (2*\#_2(w_2)) \}$ $\Sigma = \{0,1,2\} \cup \{@\} $ I need to prove that this language is not ...
1
vote
1answer
31 views

How to draw a DFA from regular expression a*b*?

I'm doing some exercises to the topic DFA and noticed, that most solutions I could find to a specific language do not look like my own solution to it and I'm kinda confused. The condition of the L is {...
2
votes
1answer
35 views

Understanding the second condition of the pumping lemma

I'm confused about a very specific detail in the following solution The second condition of the pumping lemma states that |xy| <= p. We also know that w = xyz . In this case , w = $0^p1^p2^p $ ...
0
votes
0answers
16 views

Show that an FSA is equivalent to another FSA with only one initial state

Let $M = (Q, I, T, \mathcal{E})$. Construct $M' = (Q', I', T', \mathcal{E}')$ where $Q' = Q \cup \{q_0\},$ $I'=\{q_0\},$ $\mathcal{E}' = \mathcal{E} \cup \{(q_0, a, q) \mid \exists q_{I} \in I, (...
0
votes
1answer
37 views

Finding a regular expression for a given language

I'm told that given the alphabet {a,b} I have to find the regular expression for a language that has at most two a's I came up ...
1
vote
1answer
22 views

Necessary and Sufficient Conditions for x and A

Having $A^* - \{x\} = A^+$ while $A$ being a language over $\{a,b\}$ and $x∈\{a,b\}^*$ This is only true $iff$ $x = ε$ So I did a proof: $A^* -\{ ε \} = A^+\\ A^*-\{ε\}+\{ε\}=A^++\{ε\}\\ A^*=A^*\...
3
votes
2answers
42 views

How Can The Following Language Possibly Be Regular?

$L =$ {$(01)^a$$x(10)^b$ | $a=b, b > 0, x∈${$0,1$}*} This is a question where according to the key, yes, the language is regular, but no explanation is given. However, if $a=b$, then this can be ...
2
votes
1answer
47 views

What's wrong with this proof? (Regular languages)

We want to show that for any fixed $n$, $\bigcup_{i=1}^n L_i$ is regular when all $L_i$ are regular. I understand that this is only true for finite $n$. However, what's wrong with the following ...
1
vote
1answer
85 views

Proving $ww^Ru$ is not a regular language with Pumping Lemma

I'm trying to prove that $L=\{ww^Ru:w,u∈\{a,b\}^+\}$ ($w^R$ is the reverse of $w$) $w$ and $u$ cannot be empty strings. I want to prove this by using pumping lemma but I cannot find a good starting ...
0
votes
1answer
31 views

Regular Language and Non-Regular Language

Regular Language as I know of, is something that can be defined by a FSM. Non-Regular Language is something that consists of repetition which cannot be stored by the FSM. I have found out that L( ...
0
votes
0answers
18 views

prove that given language is not regular.

So i need to prove that the language $L=${${a^ib^j: gcd(i,j)=1}$} is not regular. For which i chose the string $w=a^{m!}b^p$ where $p>m!$ and is a prime number. clearly $m!$ and p are co-prime so ...
1
vote
1answer
43 views

How to proof language which consists of concatenation of strings in palindrome is not a regular language?

How to proof $L = \{ x \in \Sigma^* | x=y_1\cdot y_2 \cdot \dots y_m, \exists m \ge 1 \,\land \forall y_i \in \text{Palindrome over } \Sigma^*\}$ is not a regular language? My attempted is $\text{Let ...
0
votes
1answer
40 views

If $A$ is not a regular language and $B$ is a regular language and $B \neq \varnothing$, does $AB$ is not regular language?

I am trying to proof that $L = \{ 0^11^2...0^{n-1}1^n0^{n-1}...1^20^1\}$ where $n >= 0$ is not a regular language. So my method is to put $S = 0^11^2...0^{n-1}$ $W = S1^nS^R$ And then proof $S^...
1
vote
2answers
26 views

Showing that a Language is regular using a state machine diagram

I'm in my first few weeks of taking a theoretical course at my school and was wondering what is wrong with my answer to this question. I've been told to show that the language: L = {x | x has even ...
2
votes
1answer
47 views

String powers. Lemma 1.3.5 in word processing in groups. Epstein.

I can't understand this demonstration. Why if ${w'}_1$ is different from ´${w'}_2$ then we have that $f(u)$ and $v'$ are powers of some string $z$?
2
votes
1answer
38 views

What is open first in formal languages

What is a set of values that come from $(1^*0^*)^*$? Is it set of any number of combinations of any number of 1 and any number of 0. Like we have 10 inside of brackets and than repeat it as much as ...
0
votes
1answer
174 views

Simply starred language. $\left\{(ab)^n:n\in\mathbb{N}\right\}$ it is regular?

I have many doubts with this. First: In the definition, let $A=\left\{x\right\}$ one-letter alphabet. Then $A^{\ast}$ is simply starred? Second: In the definition, I know that $\left\{a^nb^n: n \in \...
0
votes
1answer
39 views

square-free word

I am trying to understand one concept. Is it possible to have a square-free(no subwords ss) word in a language of just $\{0,1\}$ of any given length ( $10^{100}$ for instance). I found out a Thue–...
1
vote
1answer
17 views

Proving commutativeness of an operator using structural induction

Let's suppose we have this language that defines natural numbers: $$ \Bbb{N} = O : S \Bbb{N}$$ So a number can either be $O$ (zero) or $S \Bbb{N}$ (the successor of a natural). Let's define the ...
2
votes
1answer
34 views

Is it ALWAYS true that if L= {w|odd(w) is regular} then L is regular.

I have been stuck on this problem for a couple of hours and can't seem to figure it out.A bit of a hand would be nice.So we have that odd(w) is the letters from the string w that are in odd positions ...
0
votes
1answer
52 views

Finite automata where the difference in the number of a's and b's is less than three

Given the following problem: Design a finite automata that only recognizes the strings of the language $L$ of the alphabet $\sum = \{ a, b \}$ such that each string does not contain any prefixes ...
2
votes
1answer
31 views

Given a finite automaton determine if it is deterministic and indicate regular expression

Given the finite automaton: Make the transition table and indicate if it is deterministic or not. Indicate which of the following regular expressions corresponds to the language recognized by the ...
0
votes
1answer
78 views

Prove that $L= \{w|$ $w $ ends with a palindrome of length greater than or equal to $4\}$ is nonregular using the pumping lemma.

The alphabet is $\{a, b\}$ Hi, I tried this: Assume to the contrary that $L$ is regular. Let $p$ be the pumping length given by the pumping lemma. Let $s$ be the string $a^{p}ba^{p}$. Because $s$ is ...
0
votes
1answer
42 views

Regular expression: Difference between $\emptyset$-concate and $\lambda$-concate?

Given the definition below, is that the concatenation $\emptyset A$ the same as $\lambda A,$ given $A$ a regular expression? If not, what's the difference? My guess is that if I take concatenation $AB$...
0
votes
2answers
40 views

What is regular expression and its NFA of a word that accept any number that is divisible by 5?

I was given a task to find RE and NFA for a word that is divisible by 5. ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} String passed to RE could be of any length You may ...
0
votes
1answer
50 views

Prove $L$ is context free if $L_1$, $L_2$, $L_3$ are regular by building a suitable grammar

Given $L_1$, $L_2$, $L_3$ are regular, prove that: $$L=\{w_1w_2w_3\space|\space w_i\in L_i\space \land\space|w_1|+|w_2|=|w_3| \}$$ is context free by building a suitable context free grammar. I know ...