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-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
0answers
12 views

How can we modify the proof if the alphabet in $M_1$ and the alphabet in $M_2$ are not the same? (Regular Language, Sipser)

I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser. How can we modify the proof if the alphabet in $M_1$ and the alphabet in $M_2$ are not the same? We ...
0
votes
1answer
20 views

regular language proof

Question: Prove that a finite language is a regular language. How would I go about solving this? I tried my own approach (below) but didn't get far because I don't understand how I am supposed to ...
2
votes
1answer
23 views

language kleene star union not equal to union of language kleene star

Find languages A and B such that $A^* \cup B^* \neq (A \cup B)^*$. Is this even possible? I tried: $A:\{$ $\epsilon $ $\}$ and B:$\{$ $1$ $\}$ $A^*= \{\epsilon \}$ and $B^*=\{\epsilon,1,11,111,.......
1
vote
0answers
36 views

Why is the singleton language {x} regular?

So in most definitions of a regular language, it states that Ø and {x} are regular. I am curious as to why the singleton language {x} is regular, like what proof or reasoning for it to be a regular ...
1
vote
2answers
41 views

Pumping lemma, L={WW^R | W can be {1}+}

im trying to find out, if L is regular or not using pumping lemma. I have L={WW^R | W can be {1}+} So possible strings would be 11, 1111, 111111. In every cases i have googled so far are examples ...
-2
votes
0answers
30 views

How to prove that regular languages are closed under an operation

How to show that regular languages are closed under the operation $C$ defined as follows $$ C(B_1, B_2) = \{w \in A^* \mid \text{ there exists } x \in B_2 \text{ such that } wx \in B_1 \} $$ I was ...
0
votes
0answers
27 views

How to prove that concatenation of words from regular languages is a regular language using left quotient?

Let $$ L=\{x\in \Sigma^*\big|x=uvw, \\u,v,w \in \Sigma^*,\\u\in L_1,\\v\in L_1,\\uw\in L_2\} $$ where $L_1, L_2$ are regular languages over $\sum^*$. Prove that $L$ is also regular. I'd like to ...
-1
votes
1answer
43 views

Regular Grammar

Devise a regular grammar in normal form that generates the language L. Let L be the language consisting of all binary numbers divisible by 4. I know the different aspects needed to be generated: ...
0
votes
0answers
33 views

Context-Free grammar - Normal form

Termials = a,b,c. non-Termials = A,S. Production Rules: (1) S → aS (2) S → bA (3) A → bA (4) A → cA (5) A → c (6) S → a How do you write the following in normal form, I understand that it is ...
0
votes
0answers
24 views

Proof a language is not regulary

I need to proof that a language is not regulary, could this working? $Proof\quad that\quad N\quad =\quad \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+1 }|m,l\quad \in \quad N \right\} \quad with\quad \...
1
vote
1answer
22 views

If a language and its complement are context-free, is it regular?

If both $L$ and $\overline{L}$ are context-free, is $L$ necessarily regular?
0
votes
0answers
24 views

number of words in language $L \subset \Sigma$

I had my lecture today about decidable languages and as I am reviewing the material I have from the university, I got quite confused about the following definition: $\emptyset$ doesn't contain any ...
2
votes
2answers
82 views

Given a transition table do digraph, determine if it is DFA or NFA and build grammar

For the next transition table: $$\begin{array}{|c|c|c|c|}\hline&0&1&2\\\hline a&a&b&d\\\hline b&a&b&c\\\hline c&c&d&a\\\hline d&c&c&a\\\...
2
votes
1answer
38 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\: ...
1
vote
1answer
38 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
21 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
49 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
18 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?
0
votes
1answer
11 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
22 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
35 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
31 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
36 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
22 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
43 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
31 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
78 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
54 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
64 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
63 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
57 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
66 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
92 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
38 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
21 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
39 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
45 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
49 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
115 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
87 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
68 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
27 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$?