Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,240
questions
3
votes
1answer
99 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
94 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
37 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
35 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
49 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
25 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
29 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
71 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
140 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
147 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
66 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
41 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
879 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
142 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
63 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
112 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
254 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 ...
0
votes
1answer
55 views
DFA for language of all strings avoiding 'aa'
I'm trying to draw a dfa for this description
The set of strings over {a, b, c} that do not contain the substring aa,
current issue i'm facing is how many states to start with, any help how to ...
0
votes
0answers
36 views
Did I prove the language is not regular?
I am trying to prove the following language that is not regular.
I used Pumping Lemma proof and my proof goes as follows:
Assume that L is regular and let p be the constant of Pumping-Lemma.
This ...
2
votes
3answers
266 views
Is {a^n: n is a product of exactly two primes} regular?
I am struggling to prove the following question.
$L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$
I feel like the language is not regular but I am having trouble proving it. I tried ...
