# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,816 questions
Filter by
Sorted by
Tagged with
17 views

### DFA testing exercice ASAP please [duplicate]

I have a question : If my word can be only AA or BB or A or B how i will write my regular expression ? And if 0 is a par number it also may be to include ? it is something like this : A|B|epsilon) (AA|...
1 vote
38 views

### Communication complexity of Dyck language

I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
54 views

So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ... 36 views

### L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y

How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days. L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
35 views

### How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i}

How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
21 views

### Lambda Calculus with State

I want to define a typed domain-specific lambda calculus which can simulate the sequence execution like common programming language. I wonder how to give its corresponding BNF, can I use ...
57 views

### Is L={0^n 1^n ∣n≥0} context free language?

I looked through many sources which give this as an example for cfl. It also makes sense according to this: But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can ...
43 views

### Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
1 vote
18 views

1 vote
168 views

### How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?

I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL. In any case, i ...
38 views

### Is the set of all strings over $\Sigma$ countably infinite or not?

Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
980 views

### Is the language given by the regex (ab)* star-free?

I was reading about star-free languages recently and a common example of a non-star free language is the one given by (aa)*. I was wondering if (ab)* would also work (for an alphabet of two symbols ... 78 views

### Can you verify the end of a function declaration through syntax analysis?

In some languages, it is expected that a function declaration be terminated by syntax that includes the function name. For example, in MODULA-2, a function is declared as shown below: PROCEDURE P ; ...
25 views

### Confused about decomposition in Context Free Pumping lemma

Okay so here's my current solution for the question that asks whether the language is context free: $$L = { a^nb^{3n}c^n | \, n \geq 0 }$$ Assume by contradiction that L is context-free. Let p be ...
1k views

### Are 2 independent PDAs equivalent to a turing machine?

I was thinking about the language $a^nb^nc^n$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $a$ and $b$ and the second for $b$ and $c$ and ...
13 views

### Show that if <S2;S2,s> =>* <S2,s'>, it is not necessarily the case that <S1,s> =>* s'

I am trying to solve this proof. In structural semantics I need to proof that: ...
1 vote
72 views

### Is $L=\{1^n2^n3^m : n\neq m\}$ context free?

Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free? I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
1 vote
75 views

1 vote
26 views

### Can a modified Turing Machine be Turing-Complete if its Program and Data memory share the same tape?

I've been working on a fun esolang that operates under the idea that it only has program memory (an infinite, sequential list of registers that instructions and instruction arguments are loaded into). ...
36 views

### Finding a DFA with same language as given $\epsilon$-NFA

Consider the following automaton. How does one find a DFA with an equivalent language using an algorithm? In particular, I was requested to use the algorithm described in the answer to this question. ...
170 views

### Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it

Were w is any string composed over the alphabet $\Sigma = \{0,1\}$. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
125 views

### nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive

I have a question I need to give the NFA of the following language: L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa ...
454 views

### Prove or disprove that two regular languages are equivalent

I have $L_1=\{b^*+b^*a(b+ab^*a)^*ab^*\}$ and $L_2=\{(b^*ab^*a)^*b^*\}$. I want to prove or disprove that they are equivalent. I have proved that $L_2\subseteq L_1$ and I tried to transform the second ...
1 vote
50 views

### Regex to DFA - How do I implement parsing preferences in regex search?

I've tried a to implement a Regex to DFA converter, and it works, so far, but I don't understand how to implement "parsing preferences" in the DFA. A classic example is $a^*$. This regex is ...
Consider the following grammar $G$: $$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$ Decide if ...