2022 Developer Survey is open! Take survey.

# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

2,631 questions
Filter by
Sorted by
Tagged with
34 views

### The Language of All Palindromes - Is it CFL?

Regarding $L=\{ww^R~|~w\in\Sigma^*\}$ - The language of all palindromes. Is it a CFL? I think it is, because if we take any $\Sigma$, for example $\Sigma=\{a,b\}$, then it certainty is. CFL are closed ...
37 views

### Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

I want to construct a context-free grammar for this language: \begin{align*} L = \{uc^nd^nv\mid \ u,v \in \{a,b\}^* \text{ and the number of a's and b's in } uv \text{ are equal}\} \end{align*} I know ...
31 views

### Is there an alternative for the formal language theory that could be used for flowchart diagrams?

I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
1 vote
87 views

36 views

### Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode [closed]

Let $L=\{b^ma^n \mid \text{$m$and$n$are coprime} \}$. Using Nerode's theorem, prove that $L$ is irregular. From Nerode's theorem I know that $L$ is regular if and only if the number of equivalence ...
1 vote
56 views

### Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's

Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's. So far, I have $(aa)^*a((b+\varepsilon)(aa)^*)^4$, but I don't think this ...
83 views

### How would I show function $f(x)=4x$ is Turing computable?

How to show $f: \mathbb{N} \to\mathbb{N}$ with $f(x)=4x$ where $x$ is in the set of natural numbers $x\in\mathbb{N}$) is Turing Computable? My guess is obviously there is a finite number of operations ...
51 views

### Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$

Turing Machine for the Language $L=\{(a^n)b(a^n)b(a^n) | n\geq0\}$ Here is what I have tried: 1. Starting State Read $a$, Write $x$, Move Right, Go To 2 Read $x$, Write $x$, Move Right, Go To 1 Read <...
2k views

### Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
54 views

### Prove/find context free grammar is unambiguous for the language $L$

I am trying to find a grammar and prove that it is unambiguous for the language $L$, where $$L = \{ w \in \{a,b\}^+; |w|_a = |w|_b \}$$ Essentially: word $w$ contains at least one $a$ and $b$; where ...
512 views

37 views

### How to convert a null state transition in nfa to dfa

i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA) I have tried creating the NFA for the regular expression as given in the above image, From the regular ...
1 vote
21 views

### How does checking correctness with Weakest Preconditions work?

We have this example: {true} assume x > 1; y := x * 2; z := x + 2; assert y > z; {true} They then show this: ...
105 views

### NFA where there are two 0s separated by a multiple of 4

I've been following Automata and Formal Languages in my college and I came across this particular exercise. While the solution presented seems correct, I take on Automata Tutor trying this exercise a ...
55 views

### How does one prove that DEC does not parameterize DEC?

The $n$th slice of a set $A \subseteq \Sigma^{*}$ is defined as: $$A_n = \{x \in \Sigma^{*}\mid\langle n,x\rangle \in A\}$$ The definition of parameterization is as follows - $C$ parameterizes $D$ (...
132 views

### Useless states in a PDA

I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads: 4.22 A useless state in a pushdown automaton is never entered on any input string. Consider the ...
1 vote
Given the language $D = \{x^n y^n y^m \mid n,m \geq 0\}$, I have applied the pumping lemma with $k>0$, $n=k$ and $m=0$ and found a word $z = x^{k+q} y^k$ with $q>0$ that does not belong to $D$. ...
### DFA for $a+b=c$, where $a,b,c$ are input in parallel
I've faced this question in my homework, it's a bonus question so it's harder than I could do now with my current knowledge, so if anyone could help I'll be thankful. We're given $\Sigma=\{0,1\}^3$. ...