Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
22 views

Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathcal{P}$?

My professor said that the non-regular language $L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belongs to $\mathcal{P}$. I do understand that all regular languages belong to $\mathcal{P}$ as ...
1
vote
1answer
38 views

What is the logical reasoning behind Arden's Theorem proof of unique solution?

Here is the proof for Arden's Theorem assertion that R=QP* is the unique (only solution) to R=Q+RP. My question is: what is the logical reasoning to prove that any equation is the unique (only ...
-1
votes
0answers
9 views

How to tell if a language is regular or context free based on its description [duplicate]

I dont understand how to tell if a language is regular or context free by just looking at its description. For example question 1.2: how is it not regular? can't we create a regular expression for ...
3
votes
1answer
101 views

Regular expression for strings not starting with 10

How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?
2
votes
1answer
34 views

Show that language of distinct binary strings is irregular

Let $Σ =\{\textbf{[},\textbf{]},\textbf{,},\textbf{0},\textbf{1}\}$, and let $L⊂Σ^*$ be the language containing list representations of finite sets of binary strings: i.e., every string $x∈L$ is of ...
4
votes
1answer
95 views

How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
1
vote
1answer
40 views

Is there any base representation that produces a non-regular language for set S?

To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc. Given the set $S$ of natural numbers such that $S = \{2^i| i \in \mathbb{N}\}$ prove that ...
-1
votes
0answers
24 views

Show that this language L' is regular [duplicate]

I'm not even sure where to begin with this. The language given is: L' = { x∈Σ* | ∃y∈Σ*, |x|=|y| and xy ∈ L}. Basically, L' consists of the first halves of the strings in L, where L is a regular ...
1
vote
0answers
36 views

Prove the ternary representation of there natural numbers is not a regular language [duplicate]

Choose some set in the natural numbers such that the language formed by the set under binary representation is a regular language, but is not regular under any other language formed by some base. ...
3
votes
1answer
50 views

Prove the equivalence of regular expressions

I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated. Suppose there exists regular expressions R, S and T. ...
0
votes
0answers
26 views

Prove that any PDA/CF language with 1 character is regular [duplicate]

I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
0
votes
0answers
34 views

Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]

I am able to form the regular expression but I am not confident with the grammar. I have tried the following: S-->aaaS|bS|b|lambda Regular expression is given by: ...
2
votes
1answer
72 views

Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
3
votes
2answers
142 views

Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a

I have created the following solution but its left recursive: S--> a|bSc|cSb|Sbc Also it is not accepting: "ab" or "cba" or "abb" or abc. Somebody please guide me. Zulfi.
-1
votes
0answers
16 views

Regular expression required [duplicate]

Give a regular expression for L={a^n b^m |n>=1,m>=1,nm>=3} I tried something like this: a(a)* . bbb(b)*
0
votes
1answer
44 views

Statements about homomorphisms

Consider the following expressions about homomorphisms and show if the statements are true or not. Σ={0,1}, L1 and L2 are Languages ⊆ Σ*, and ᵠ is a homomorphism ᵠ: Σ* → Σ*. ᵠ(L1 ∪ L2) = ᵠ(L1) ∪ ᵠ(...
2
votes
3answers
68 views

How to prove that this language is not regular?

Given a language $L$ over the alphabet { 0, 1, [, ,, <...
0
votes
0answers
21 views

What exactly is “pattern matching”?

I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions. But is there a precise definition? In particular, it seems that it has to do with ...
1
vote
1answer
24 views

Given a regular language, calculate its equivalence classes

I was given the following regular language: For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character from the end is 1. I know it's regular because it can be ...
3
votes
3answers
149 views

Is it possible that the subtraction between two undecidable languages is regular?

If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set? What's ...
1
vote
1answer
68 views

Prove that $\texttt{prefix}(L)$ is regular

Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular. So far I have provided that the grammar to produce this language ...
0
votes
1answer
25 views

Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
0
votes
0answers
27 views

What is a Regular BNF Grammar and a Regular Expression for (simple) Resource Identifiers?

I was trying to make a regular grammar for resource identifier described as follows: Consider the set of all strings over the alphabet $\{ a, b, / , . \}$ that represent an RI (resource ...
0
votes
1answer
43 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
-2
votes
2answers
62 views

$L_1 ∩ L_2$ is not regular while $L_1$ is regular and $L_2$ is not regular language

Could you give me an example of languages $L_1$ (regular) and $L_2$ (not regular) where $L_1 \cap L_2$ is not regular?
5
votes
3answers
881 views

How to determine minimum word length of regular language

Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$? A straightforward example: Let's ...
2
votes
1answer
149 views

Example of non-regular context free language L such that prefix(L) is regular

Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L. What can be an example of non-regular language L such that language of it's ...
4
votes
1answer
37 views

Is unification over regular expression equations doable?

By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations. Generalizing ...
1
vote
2answers
42 views

Pumping Lemma with Prime Number [closed]

$\text {Could someone please help me with this proof: }$ $L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$ $\text {Maybe we can say, that } w=a^{n}d^{...
0
votes
1answer
54 views

Every regular language has a finite index

For a language $L$ over an alphabet $\Sigma$, we say that two words $v,w \in \Sigma^*$ are equivalent, denoted $v\sim w$, if for every word $z \in \Sigma^*$, $vz \in L$ iff $wz \in L$. We define $[w]...
0
votes
1answer
41 views

Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
0
votes
1answer
27 views

Regular expression for containing 010 as a subword

I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand. I managed to solve the following question: ...
1
vote
1answer
28 views

Closure of regular languages under “inverse second half”

Theorem. Show that if $L$ is regular, then so is $$ \varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\...
0
votes
0answers
26 views

Proving that the language of regular expressions is not regular

Prove that the language consisting of all valid regular expressions is not regular. I am approaching this using the Myhill-Nerode Theorem as follows: I am trying to find a pairwise distinguishable ...
2
votes
1answer
48 views

Regular expression for language that does not accept x string (3 letters, |x|=3)

The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
1
vote
1answer
64 views

Can a dfa return only the final state?

I am given an assignment to design a tiny arithmetic unit (from 0 to 15 inclusive) start with 0 and using a DFA. The operations are as follow: increment x+1 and if x+1 is larger than 15 then x+1 ...
1
vote
1answer
26 views

Prove its not a regular language [duplicate]

I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language. Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language. I can prove it with pumping ...
2
votes
2answers
106 views

Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
1
vote
1answer
102 views

Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
0
votes
0answers
28 views

Backwards and forwards automata languages compared with regular languages

Is every language accepted by a BAFDA regular? I am not even sure what the answer is. I tried thinking around canonical examples of non-regular languages (like $0^n1^n$ or $\{ww | w \in \{0,1\}^{*}\}$ ...
4
votes
2answers
60 views

Finding the number of distinct strings in regular expression

Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
22
votes
6answers
11k views

Why is English not a regular language?

Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., ...
2
votes
1answer
27 views

totally ordered semigroups

Given a semigroup is it possible to give a total order to it? If not possible in the general case then what about the case of finitely generated finite semigroups? Does there exist a natural ...
0
votes
1answer
56 views

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
0
votes
0answers
35 views

Regular expression for set of strings with no two consecutive 1's? [duplicate]

I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's. I'm also wondering if there is a pattern that could be extended to ...
3
votes
1answer
116 views

How do I solve these questions regarding homomorphism?

Questions: Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
-1
votes
1answer
46 views

Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...
0
votes
0answers
44 views

If L is a regular language, how to show that cut(L) is not necessarily regular? [duplicate]

Given that L is a regular language. How do I show that cut(L) = {ac | abc ∈ L and |a| = |b| = |c|} is not necessarily regular? My thought process is that this problem can be re-written as: cut(L) = {...
3
votes
1answer
73 views

Prove that there isn't a DFA characterized by (a*)+(b*) for which |Q| = 3

Let $R=(a*)+(b*)$ be a regular expression. Prove that there cannot exist any DFA $M=(Q,\Sigma,\delta , q0, A)$ such that $|Q| = 3$ and $L(M)=L(R)$. The problem is, I think IT IS possible to construct ...
2
votes
1answer
255 views

If R is a regular language, is $R^3= R \circ R \circ R$ also regular?

My understanding of a regular language is that for a language to be formal, it must be able to be represented by a DFA or NFA. To prove a language is not regular you can use the pumping lemma to get a ...