Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
433
questions
94
votes
10
answers
162k
views
How to prove that a language is not regular?
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
- 71k
96
votes
5
answers
94k
views
How to prove that a language is not context-free?
We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
- 71k
52
votes
8
answers
112k
views
How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?
For instance, if I am given that $L$ is regular,
how can I prove that ...
- 869
28
votes
2
answers
42k
views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
D.W.♦
- 143k
136
votes
4
answers
197k
views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
- 71k
25
votes
1
answer
8k
views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
- 71k
48
votes
2
answers
9k
views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
- 29.2k
49
votes
1
answer
21k
views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
- 20k
5
votes
2
answers
12k
views
How do I find a regular expression for a particular language?
I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
D.W.♦
- 143k
74
votes
1
answer
14k
views
Language theoretic comparison of LL and LR grammars
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
- 71k
21
votes
1
answer
6k
views
Languages that satisfy the pumping lemma but aren't regular?
Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ ...
- 13.7k
44
votes
2
answers
2k
views
Determining capabilities of a min-heap (or other exotic) state machines
See the end of this post for some clarification on the definition(s) of min-heap automata.
One can imagine using a variety of data structures for storing information for use by state machines. For ...
- 12.6k
16
votes
3
answers
3k
views
What are the possible sets of word lengths in a regular language?
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$
Which sets of integers can be the length set of a regular language?...
14
votes
2
answers
2k
views
Closure against right quotient with a fixed language
I'd really love your help with the following:
For any fixed $L_2$ I need to decide whether there is closure under the following operators:
$A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$
$A_l(L)=\{...
- 1,667
6
votes
2
answers
8k
views
Converting to CFG from a CFL? [duplicate]
I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.
Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
- 173
8
votes
1
answer
9k
views
Prove that regular languages are closed under the cycle operator
I've got in a few days an exam and have problems to solve this task.
Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation
$\operatorname{cycle}(L) = \{ xy \mid x,y\in \...
- 501
8
votes
2
answers
22k
views
Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$
I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb \...
- 115
29
votes
3
answers
2k
views
Which languages do Perl-compatible regular expressions recognize?
As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that ...
- 549
11
votes
1
answer
6k
views
If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$
I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
- 111
15
votes
1
answer
8k
views
Single-tape Turing Machines with write-protected input recognize only Regular Languages
Here is the problem:
Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages.
My idea is to prove that this ...
- 345
9
votes
3
answers
902
views
Context-sensitive grammar for the language of words concatenated with themselves
I'm looking for a context-sensitive grammar that describes the following language:
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .
I've got problems with the fact that no rules such as $X \to \...
- 91
10
votes
3
answers
3k
views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
- 201
28
votes
3
answers
12k
views
Pumping lemma for simple finite regular languages
Wikipedia has the following definition of the pumping lemma for regular langauges...
Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1
depending only on $L$ such that every ...
- 843
17
votes
3
answers
8k
views
Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
- 173
12
votes
7
answers
2k
views
Is $A$ regular if $A^{2}$ is regular?
If $A^2$ is regular, does it follow that $A$ is regular?
My attempt on a proof:
Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.
Since concatenation of two non-regular ...
- 321
9
votes
1
answer
551
views
How can ws with |w| = |s| and w ≠ s be context-free while w#s is not?
Why does (if so) the seperator $\#$ is making a difference between the two languages ?
Let say:
$L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \}$
$L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, ...
- 246
12
votes
2
answers
4k
views
If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?
Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular?
If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular.
Also ...
- 239
5
votes
3
answers
5k
views
Is {wxw^r} a regular language?
Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why?
The notation $W^{\mathrm{R}}$ means the reverse string of $W$?
If we consider the best answer in this solution, ...
- 335
10
votes
5
answers
1k
views
Language of the values of an affine function
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
30
votes
4
answers
92k
views
How to show that a "reversed" regular language is regular
I'm stuck on the following question:
"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
- 303
17
votes
1
answer
10k
views
Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
- 305
5
votes
2
answers
2k
views
Pumping lemma: if you can keep pumping, what does this tell you?
Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
- 51
8
votes
1
answer
2k
views
Kleene star of an infinite unary language always yields a regular language [duplicate]
Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$.
Thus $L$ consists of sequences of $a$ of all lengths, including a sequence
of length $0$. Let $L_2$ be ...
- 193
4
votes
3
answers
7k
views
Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:
$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$
My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
- 51
19
votes
3
answers
10k
views
Is there any uncountable Turing decidable language?
There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
39
votes
2
answers
6k
views
Are there inherently ambiguous and deterministic context-free languages?
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language ...
- 12.6k
16
votes
2
answers
4k
views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
- 355
12
votes
3
answers
7k
views
Easy proof for context-free languages being closed under cyclic shift
The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
- 27.7k
8
votes
3
answers
6k
views
Proving that any CF language over a 1 letter alphabet is regular
I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:
Let $L$ be ...
- 119
7
votes
1
answer
5k
views
DFA for a strings whose every subsequence of length five has at least two zeroes
I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
- 337
4
votes
3
answers
3k
views
Show that regular languages are closed under Mix operations
Let $L_1, L_2$, two regular languages and the operations:
$$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
- 377
3
votes
1
answer
2k
views
Context Free Grammar for language L
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$
I'm trying to write a grammar for this language?
I tried this:
$S \to S_1 \mid S_2 \\
S_1 \to aXb ...
- 115
2
votes
1
answer
3k
views
are regular languages closed under division
I am trying to solve this question which appeared in previous exam paper
Can someone help me what i am failing to understand
For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
- 145
2
votes
1
answer
1k
views
What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?
I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language ...
- 23
23
votes
2
answers
25k
views
Is the complement of { ww | ... } context-free?
Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not?
I'...
- 701
15
votes
2
answers
2k
views
Number of words of a given length in a regular language
Is there an algebraic characterization of the number of words of a given length in a regular language?
Wikipedia states a result somewhat imprecisely:
For any regular language $L$ there exist ...
11
votes
1
answer
2k
views
Algorithm to test whether a language is regular
Is there an algorithm/systematic procedure to test whether a language is regular?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\...
D.W.♦
- 143k
10
votes
5
answers
2k
views
Is there a known method for constructing a grammar given a finite set of finite strings?
From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?
If given n strings of m length, it should be possible ...
- 260
11
votes
1
answer
382
views
Expressiveness of modern regular expressions
I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like <...
- 211
3
votes
1
answer
2k
views
Is regularity of the language accepted by a given Turing machine a semi-decidable property?
Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
- 219