# Questions tagged [automata]

Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

1,672 questions
Filter by
Sorted by
Tagged with
7 views

### Pumping lemma for context-free languages: Importance of length restriction

(from 'An Introduction to Formal Languages and Automata' by Peter Linz) What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction ...
39 views

13 views

### Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$ (without using the complement closure property). My thoughts: I understand ...
34 views

### Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$. My thoughts: I understand that $L_2 = \{0^n1^n: n\geq 0\}$ can be shown to be ...
1 vote
43 views

### Prove a subset of a regular language is regular, context-free but not regular or not context free

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
31 views

### List equivalence relations of language

I've been trying to solve the following problem: List all equivalence relations of the following language: $L=\{w\in \{0,1,2\}^* | w=u0v ; u,v \in \{1,2\}^*; \#_1(u)>\#_2(u); \#_2(v)=|u| \}$ So, ...
1 vote
67 views

2k views

### Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language? $\#_a(w)$ is the number of $a$'s in $w$. So far every language that I saw containing modulo was a ...
111 views

### in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?

I'm struggling with the definitions of the push-down automata. In 2-DPDA and 3-DPDA, what do the numbers 2 and 3 stand for: for the number of stacks or of read-only tapes (and hence RO heads) ? ...
31 views

### How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]

I want to show that the language $L=\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL. If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL ...
37 views

### Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?

Why is this language regular: $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$? Where $\#_a(w)$ is defined as the number of $a$ in $w$. Isn't that a concatenation between 2 CFL? Thanks!
74 views

### Help with two-tape Turing Machine for $L = \{ a^{n^2} | n \ge 0 \}$ - clarification needed

I came here to ask for help with a two-tape Turing machine for the following language. $L = \{ a^{n^2} | n \ge 0 \}$ I tried following the advice on this site: Turing machine that accepts L={an2|n≥1} [...
38 views

### If two states of a DFA are k-equivalent and k+1 equivalent

Let $p,q$ be two states of a DFA, such that $p\equiv_kq$ and $p\equiv_{k+1}q$. Does it mean that $p\equiv q$ ? I don't think so, because if the minimization algorithm can continue, they might be ...
30 views

### Design a linear-bounded automata

I have to design an $LBA$ the following language: $L = \{a ^ {n!} | n \geq 1\}$ I have seen two algorithms from this post with a two-tape machine and this link, but I can not figure out how to draw ...
35 views

### Let $L$ be a finite language. Show that then $L^+$ is recursively enumerable. Suggest an enumeration procedure for $L^+$

I am solving basic questions about Recursive and Recursively-Enumerable languages. I know that base on the below theorem, to prove that a language is RE we should define an Enumeration Procedure for ...
1 vote
44 views

### If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular

Prove/disprove the following claim: If $L\in RL$ then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$ I think that this is true, and my intuition is by using $L_{pq}$ s.t: For every $(p,q)\in Q\times Q$...
1 vote
185 views

### How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language

Let $L$ be a regular language. Define: $half(L)=\{x|xy\in L,|x|=|y|\}$ Prove that $half(L)$ is regular as well. I have seen a hard proof by using the DFA A of L, building a NFA B (such that every ...
87 views

### CFL with regular substitution to make a regular language

If I have a CFL, can I define a regular substitution to make it a RL? For example, if I have the language $\{a^nb^n \mid n\ge0\}:$ Define $h(a)=a$ , $h(b)=b$, then $h(L)={a^*}$ , am I right? Thanks!
67 views

50 views

### Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \}$

$L = \{a^nb^m | n \le m \le 3n \}$ This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each ...
59 views

### Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$

Could someone please help me check if my automaton is correctly designed? $$L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$$ This was an exercise from our workbook, but their solution is a ...
40 views

### show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages

prove this language verifies the conclusion of the pumping lemma show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages the problem is that I ...
50 views

### Context free grammar for $a^i b^j a^j b^i$

I recently started learning context free grammars and was working on a couple of exercise problems and couldn't really figure out how would this exactly look like. I started with: \begin{align}S&...
86 views

### Decidability of intersection of regular and decidable languages

I'm wondering if a language (A) is a decidable language and language (B) is a regular language, is the intersection between A and B regular?
1 vote
52 views

### Prove the equivalence of the modified Turing Machines and the standard Turing Machines

We have a Turing Machine that cannot write the same symbol it has read in a transition, meaning it should always alter the symbol when passing it. How can we prove that such machines have equal ...
26 views

### Prove that a Turing machine that looks to adjacent cells on left and right of a cell for decision is not weaker than normal Turing machine

We consider a Turing Machine that for a transition to apply, looks not only to the cell the head is currently on, but to its adjacent cells as well. Basically it will need to read a string of 3 ...
87 views

### Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ [duplicate]

I need to find the production rules for the following language: $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ Well, the first thing I could come up with is $S \to aSb | \epsilon$ But this only covers ...
38 views

### Union of two context-free grammars and their productions

Is it possible to create an union of two context-free grammars? I found a PDF material from the university of Iowa where they claim that it's possible but I just don't know how. They had that for ...
1 vote
72 views

### Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$ where $n,m \ge 0$ I'm very new to this so this example might be a little harder, but ...
40 views

### determining the relationship between two regular languages using the myhill nerode theorem

For a regular language $A$ with an alphabet $\Sigma$, define an equivalence relation for strings $x,y \in \Sigma^*$ by $x\equiv_A y\Leftrightarrow \,\forall w\in \Sigma^*, xw, yw\in A$ or \$xw, yw\not\...
24 views

### Considering definitions as equalities, what would happen if you continually substituted a word’s definition?

I’ve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer. The idea is to ...
1 vote