Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,427
questions
1
vote
0answers
29 views
Over every non-empty alphabet there exist languages which are non-regular
I am not sure about the answer. Intuitivly I would say that there are alphabets for which there are no non-regular languages. In particular I am thinking of languages with only one element. But I am ...
0
votes
0answers
18 views
State machine to convert from base 2 to base 10?
Is there a state machine which can convert base 2 decimals to base 10 decimals in a streaming fashion? Integers?
2
votes
1answer
24 views
Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$
I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$
I know that the two middle position should always be the ...
0
votes
1answer
33 views
Can someone please help with the proof of this?
Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that L∩ R = ∅, then prove that L∪ R is also unambiguous.
0
votes
1answer
24 views
Create an Finite Deterministic Automata for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
1
vote
2answers
58 views
Proving some subsets of a regular languages to be regular languages
I have to prove that if a language $L$ is regular then:
a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular
On this one I think I can ...
0
votes
1answer
24 views
How do i prove this language is regular? [duplicate]
I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
2
votes
1answer
54 views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
1
vote
1answer
42 views
Is this language based on the number of $a$'s of a word over alphabet ${a, b}$ context-free?
I'm trying to use the pumping lemma, to show that the language $L = {w \in \{a, b\}^+: na(w) = nb(w)}$ is not context free, where $na(w)$ is the number of $a$'s in $w$.
I have this: By contradiction, ...
0
votes
1answer
31 views
How to check if a language is not regular?
I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression
However, if the language is not regular i have to prove using the "...
0
votes
1answer
17 views
Relationship between Kleene Star of a subset of regular language and the regular language
If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
2
votes
1answer
53 views
What are the most used statements in programming (ranked)?
I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
1
vote
1answer
19 views
is the intersection of a context free language and a regular language a two way street?
I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is:
The intersection of a context-free language and a regular language always results in a context free ...
1
vote
1answer
21 views
Are regular grammar languages defined from “accepting” states?
In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
0
votes
0answers
34 views
Regular expression for all binary words avoiding 11
I am reading a book example on regular expressions and I have a trouble to get why the answer is correct.
"Write a regular expression for the regular language that contains all the strings by 0's ...
1
vote
2answers
74 views
Language of all even-length words with no 1's in left half
Consider the following language:
$$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\},$$
where $\Sigma_1 = \{0,1\}$.
I need to show that this is ...
0
votes
0answers
22 views
All string matches for regular expression [duplicate]
Given a regular expression, the ask is to find all matches in a string, str.
Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or ...
1
vote
2answers
32 views
Regular language is closed given transposition of rightmost character to leftmost
It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I'...
0
votes
1answer
35 views
Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$
Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma.
I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
1
vote
0answers
20 views
Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?
LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items.
Is ...
0
votes
0answers
14 views
Is that a regular express? Proof using closure properties or pumping theorem [duplicate]
I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me.
L = { xa yb | a ≠ b }
0
votes
1answer
31 views
Is (a+b)* and (ab)* same in finite automata?
Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... }
I am new to Finite automata and this simple notion is ...
4
votes
2answers
140 views
Does O(1) communication complexity imply that a language is regular?
Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
0
votes
2answers
33 views
What does this language notation specify?
I am given this exercise:
Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2.
w1=ε
w2=aabbcc
w3=abbccw
w4=aabbcccc
w5=...
1
vote
2answers
33 views
Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma
I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.
My idea here was to use the string $ s = (...
1
vote
1answer
31 views
Applying the Pumping Lemma to aspecific string
Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
0
votes
2answers
22 views
string concatenation vs language concatenation
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure ...
2
votes
2answers
37 views
How to we prove if a right linear language is ambiguous?
Considering the following language as an example:
$$\begin{align}
S &\rightarrow aS \mid bA \\
A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\
B &\rightarrow aB \mid \varepsilon \\
D ...
0
votes
1answer
33 views
Read regular Expression from NFA
Good evening everyone!
Can someone help me with the following task?
So we have this NFA:
I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
0
votes
1answer
110 views
What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$
What is the length of the longest string ...
0
votes
0answers
15 views
Constructing a context free grammar with starting state
I'm supposed to construct a context-free grammar generating all strings in :
{(ab)$^{m}$c$^{n}$(ba)$^{m}$ : m, n, ≥ 0}
So far I have V = {A, S, a, b, c}, Σ = {a, b, c}, and R = (1) S -> A (2) S -&...
2
votes
1answer
36 views
Is “A -> aAA” convertible to regular grammar?
I have a simple grammar as below and wonder if it is convertible to regular grammar?
If yes, what is the conversion sequence? If no, how can we prove it?
...
0
votes
1answer
24 views
minimum number of states in cross product of two minimum DFAs
If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
-1
votes
1answer
25 views
Proving of regular language [duplicate]
Is this regular or not
L = {w1w^R | w ∈ {0,1}*
(where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
1
vote
2answers
58 views
How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is ...
0
votes
0answers
86 views
Generalization of automaton - Sipser example 1.33
I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure
that my transition function is wrong. I'd like ...
6
votes
1answer
1k views
Is it possible to build any regular expression in a computer language with just 3 basic operators?
Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
1
vote
2answers
14 views
PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a ...
0
votes
0answers
24 views
Regular expressions accepted by programming languages but are not regular [duplicate]
The below definition of Regular Language is given in Wikipedia.
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language ...
1
vote
1answer
19 views
A regular language derived from another
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
35 views
Can this language be called regular?
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
70 views
How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can ...
1
vote
1answer
31 views
Regularity of a language constructed from a know regular language
I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\...
0
votes
2answers
82 views
How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?
I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.
If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
0
votes
1answer
39 views
How to apply Arden's theory to determine a regular expression
If $P=ab$ and $Q=a^*$,
how do I use Arden's theorem to determine the regular expression $R$.
I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
1
vote
1answer
28 views
Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states
Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is ...
0
votes
2answers
41 views
Can a regular expression be any string from the language described by it? [closed]
Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
2
votes
2answers
47 views
Proving non-regularity via syntactic congruence classes?
Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation:
$$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$
One ...
3
votes
0answers
37 views
BNF rule to regular expression
I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression.
(With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
1
vote
1answer
119 views
Check if a NFA accepts a string of non-prime length
Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.
My ...
