Questions related to formal languages, grammars, and automata theory
16
votes
5answers
4k 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 ...
23
votes
4answers
3k 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 ...
12
votes
4answers
4k 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. The other direction seems to be more tedious, though, and sometimes the resulting ...
23
votes
2answers
441 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 ...
6
votes
3answers
273 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 ...
14
votes
1answer
434 views
Show that $\{xy \mid |x| = |y|, x\neq 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, ...
8
votes
2answers
298 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\}$
...
2
votes
2answers
123 views
Context Free Grammar for language $L=\{a^ib^j \mid i,j \ge 0; i \ne 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 ...
9
votes
4answers
2k 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 ...
7
votes
5answers
349 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 multiples of $a$ plus a ...
0
votes
1answer
164 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 ...
16
votes
1answer
2k 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 ...
7
votes
3answers
589 views
Using Pumping Lemma to prove language is not regular
I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular.
This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p ...
6
votes
1answer
91 views
Are context-free languages in $a^*b^*$ closed under complement?
The context-free languages are not closed under complement, we know that.
As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
5
votes
3answers
613 views
operations that aren't closed for undecidable languages
Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...
