0
votes
3answers
148 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
2
votes
1answer
53 views

Proving that the continuation of a non-regular language is not ω-regular

I want to prove that a language is not $\omega$-regular. The language I'm working with can be defined as: $$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$ where ...
5
votes
1answer
148 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 ...
1
vote
1answer
103 views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...
13
votes
4answers
501 views

Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
3
votes
1answer
399 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 ...
5
votes
2answers
259 views

Proof-sketch on the language accepted by a Turing machine

Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$
0
votes
0answers
44 views

How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$ Prove $G_n$ is sub-productions from $2n^2 ...
5
votes
1answer
402 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$ ...
4
votes
1answer
90 views

What are some good hints for proving non-regularity with the pumping lemma?

My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \{a^{n} ...
2
votes
2answers
838 views

How to show that given language is unambiguous

Given following grammar: $$ \begin{align} S \rightarrow &A1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$ How can I show that ...
2
votes
2answers
192 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where ...
6
votes
3answers
255 views

Proving the language which consists of all strings in some language is the same length as some string in another language is regular

So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
4
votes
3answers
792 views

Proving a grammar only generates words whose alternating digit sums is are multiples of three

This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point. Here's the problem: The following ...
3
votes
1answer
65 views

Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite

Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language. I'm just not sure how to use their properties to formally show this. Thanks for all the ...
4
votes
2answers
2k views

Why is this example a regular language?

Consider this example (taken from this document: Showing that language is not regular): $$L = \{1^n \mid n\text{ is even}\} $$ According to the Pumping Lemma, a language $L$ is regular if : $y \ne ...
3
votes
1answer
122 views

Null Characters and Splitting the String in the Pumping Lemma

So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take ...
4
votes
1answer
727 views

Prime number CFG and Pumping Lemma

So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ...
14
votes
5answers
7k 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 ...
26
votes
5answers
12k 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 ...
39
votes
5answers
8k 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 ...