0
votes
1answer
73 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
0
votes
1answer
40 views

How does one figure out where a class of languages falls under some complexity class? [closed]

I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P? Would I have to come up with ...
1
vote
1answer
68 views

Proving that a language does not belong to a language class by using more specific instances of that language

You have a description of a language that you have to prove is regular, context free, or other. In order to prove that it does not belong to a certain class of languages, you might think that it will ...
1
vote
1answer
60 views

Prove not context free

How can we prove that: $$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$ is not context-free? The language defines $w_1$ as a sub-string of $w_2$, and they ...
1
vote
3answers
279 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
59 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 ...
8
votes
2answers
333 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
129 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 ...
14
votes
4answers
554 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 ...
2
votes
1answer
598 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
291 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
45 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
500 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
103 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
1k 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
201 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 ...
7
votes
3answers
280 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
916 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
131 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
838 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 ...
16
votes
5answers
9k 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 ...
29
votes
5answers
16k 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 ...
40
votes
5answers
10k 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 ...