Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,254
questions
2
votes
1answer
34 views
How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?
I am struggling to answer the following question:
How many different languages over the unary alphabet {a} are
recognized by 2-state DFAs?
According to the textbook, the hint was to first ...
1
vote
1answer
23 views
Algorithm to generate inputs with certain properties, but not accepted by a given regular language
General
Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\...
11
votes
2answers
2k views
Can a DFA have an unreachable state?
I am trying to prove or disprove the following statement:
If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$
So my initial thinking is to ...
2
votes
0answers
53 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
1
vote
1answer
44 views
Kleene star operations
Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{∗}$ and $𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages.
a. If $𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $L_1$.
b.Let $\Lambda \...
0
votes
1answer
34 views
Regular Language - Context Free Language
I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question
Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet
$\...
2
votes
1answer
92 views
Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular
That what I have so far, but I am not sure at all.
Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular.
Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.
Define a regular substitution $\...
1
vote
1answer
33 views
Are every 2 DFAs with $n$ states for a language $L$ isomorphic to each other?
Consider 2 DFAs both determining a language $L$. Both DFAs have the same number of states $n$. Can I then conclude that these two DFAs are isomorphic?
I think the answer is yes, because if I'd make ...
0
votes
0answers
20 views
Proving sets of regular expressions and context free grammars are decidable [duplicate]
Consider below languages:
$L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1's$\}$
$L_2=\{<G>|G$ is context free grammar which ...
6
votes
1answer
198 views
+50
How hard is finding the shortest path in a graph matching a given regular language?
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
0
votes
0answers
13 views
Which of the following are regular languages? [duplicate]
Which of the following are regular?
$\{a^lb^mc^n|10000>l>m>n\}$
$\{w| \Sigma=\{a,b,c\},10000>n_a(w)>n_b(w)>n_c(w)\}$ where $n_x(w)$ is number of $x$ in $w$
I feel 1st ...
0
votes
1answer
56 views
Why LL(1) grammar generate all regular languages?
I came across following:
Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.
I tried to get that.
Definition: Right linear ...
1
vote
1answer
30 views
Is concatenation of regular language with any other language regular?
I came across following problem:
True or false?
If $L$ is a regular and $M$ is not a regular language then $L.M$ is necessarily not regular.
The answer given was:
Consider $L$ to be $\...
1
vote
1answer
81 views
Meta text processing concept
I understand that text processing could be done in various ways on top of operating systems:
Shell utilities for processing a file (and/or a file name): tr, ...
0
votes
0answers
16 views
Regularity of language of words of prime length [duplicate]
Is the following language regular?
$$
L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}.
$$
I have to either provide a DFA (if the language is regular), or prove that it is not ...
1
vote
1answer
34 views
Showing that the class of regular languages are closed under merging / modified shuffle
Consider $ab$ and $cd$ which are two words. We merge these two into 6 possibilities: $abcd, acbd, acdb, cabd, cadb, cdab$
So in general, a merge of words/sequences $x, y ∈ Σ∗$ , is a word of length $|...
2
votes
1answer
91 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
votes
2answers
116 views
Uniqueness of solution in Arden's theorem
Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below.
My question is:
What is the logical reasoning to prove ...
3
votes
1answer
105 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
105 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
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
53 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
27 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
48 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
81 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
144 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.
2
votes
3answers
70 views
How to prove that this language is not regular?
Given a language $L$ over the alphabet { 0, 1, [, ,, <...
0
votes
0answers
22 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
28 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
158 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
97 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
29 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
30 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
83 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
67 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
885 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
242 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
39 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
52 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
62 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
51 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
28 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
29 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
28 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
49 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
65 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
29 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
125 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, ...
