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
0
votes
0
answers
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 ...
0
votes
1
answer
39
views
Is this PDA correct or an erratum? (Sipser example 2.14)
I don’t understand this state diagram. What if $n=0$? Then our input string is the empty string. We begin at $q_1$, push \$ onto the string, move to $q_2$ but then fail. So the language recognized by ...
- 1
-1
votes
0
answers
7
views
How do I show undecidability of this language using ALLCFG?
I used ALLCFG to show undecidability of EQCFG previously which was straightforward but the "or" condition in TRIVIALCFG is throwing me off. I don’t know a way to reduce TRIVIALCFG to ALLCFG.
- 1
1
vote
1
answer
56
views
determining whether a context-free language is regular
I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
- 279
-2
votes
0
answers
27
views
Context-free grammar for {a i b j |i, j ≥ 0 and i ̸= j} [duplicate]
I know the CFG for when a^ib^j, i, j>= 0 but with the additional condition of i!=j, I don't know how to do it.
0
votes
1
answer
42
views
How this state set of DFA was retrieved from the given NFA
I have this NFA:
1,{2, 3}
2,empty
3,{4}
4,empty
All the arrows in this NFA are epsilon-arrows.
I understand that all possible states that can be reached from each ...
1
vote
1
answer
38
views
Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous
Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous.
The CFG is as follows. $G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$
where $R$ consists of 6 rules:
$E\...
0
votes
1
answer
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 ...
0
votes
1
answer
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
1
answer
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$, ...
- 111
-1
votes
0
answers
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, ...
- 111
1
vote
1
answer
67
views
State Complexity of DFAs for Restricted Languages
Let $\Sigma$ be a finite alphabet. All strings below are over $\Sigma$.
Definitions:
If a string $s = vw$, then $v$ is a $\textit{prefix}$ of $s$ and $w$ is a $\textit{suffix}$ of $s$.
For a language $...
- 816
-1
votes
1
answer
30
views
Why does adding an $ \epsilon $-transition to a DFA or NFA preserve the regularity of the language?
Does adding an $ \epsilon $-transition to a deterministic finite automata preserve the regularity of the language?
Don't we have one chance to scan the word? If we choose one direction, don't we miss ...
- 101
-2
votes
1
answer
44
views
proof that every sentence obtainable by left-most derivations only when Greibach normal form
Could someone help me prove the following statement:
“For any grammar in Greibach normal form, every sentence is obtainable by left-most derivations only.”
I see that this is trivial, but I can't ...
- 55
1
vote
1
answer
37
views
substitution of same variable in context-free grammars
Above is a theorem coming from the book "Formal languages and automata" by Peter Linz concerning substitution of variables.
Could someone explain why A and B have to be different variables?
- 55
-2
votes
1
answer
45
views
Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$
Why is $L'$ a regular language?
I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
- 241
1
vote
1
answer
76
views
variable repetitions in pumping lemma for context-free languages
Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz.
The picture below is in support of the proof.
I do not ...
- 55
0
votes
0
answers
18
views
Regular, CFL, non-CFL infinite closures [duplicate]
I was wondering about infinite closure properties.
Are the Regular languages closed under infinite union? Infinite intersection?
Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
- 241
3
votes
4
answers
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 ...
- 241
2
votes
2
answers
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) ?
...
- 23
0
votes
0
answers
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 ...
- 241
2
votes
1
answer
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!
- 241
0
votes
1
answer
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}
[...
- 155
0
votes
0
answers
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 ...
- 241
0
votes
0
answers
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 ...
0
votes
1
answer
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
1
answer
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$...
- 241
1
vote
3
answers
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 ...
- 241
0
votes
2
answers
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!
- 1
-1
votes
1
answer
67
views
prove $A$ is context-free
Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \{a \in \{0,1\}^* : \text{ no character in an even position is a 0 or no character ...
- 279
2
votes
1
answer
68
views
Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free
Let $C$ be a regular language. Prove that the language $D = \{x x^R : x\in C\}$ is context-free.
It's clearly important that $C$ is regular; if the hypothesis were weakened to C being context-free, ...
- 279
-1
votes
1
answer
74
views
Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA
To those of you who saw my post from an hour ago - I deleted it because I came up with an idea.
To summarize, I have to design a PDA for this language, without using the usual method of firstly ...
- 155
2
votes
1
answer
53
views
prove that context free languages are closed under the $\circ$ operation
Prove that if $C$ and $D$ are context-free languages, then so is $C\circ D := \cup_{n\ge 0} C^n D C^n $.
I know that $\{0^n 1 0^n : n\ge 0\}$ is context free, being the intersection of $L(0^* 10^*)$ ...
- 279
0
votes
1
answer
51
views
find LR(1) items of the first state
I need to calculate the LR(1) items of the following grammar:
S -> E
E -> E + T
E -> T
T -> ID
T -> ( E )
I can not even calculate the first group {[...
- 3
1
vote
1
answer
64
views
Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
$L= \{ a^nb^m | n \le m \le 2n \}$
As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ...
- 155
1
vote
0
answers
18
views
an NFA whose corresponding DFA has at least $2^n - \alpha$ reachable states [duplicate]
Is there an NFA with n states so that the DFA resulting from the standard conversion of the NFA to a DFA has at least $2^n - \alpha$ reachable states for some integer $\alpha \ge 1$?
Let $N= (Q, \...
- 279
0
votes
1
answer
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 ...
- 155
0
votes
1
answer
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 ...
- 155
-4
votes
1
answer
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 ...
-2
votes
2
answers
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&...
- 1
-1
votes
1
answer
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
1
vote
1
answer
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 ...
0
votes
0
answers
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 ...
0
votes
1
answer
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 ...
- 155
0
votes
0
answers
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 ...
- 155
1
vote
1
answer
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 ...
- 155
0
votes
1
answer
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\...
- 279
0
votes
0
answers
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
1
answer
64
views
How to convert AFA to ε-NFA / NFA / DFA?
Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and ...
0
votes
1
answer
29
views
A language that is either fully accepted by synchronised DFAs or not at all
I am trying to understand the concept of synchronised DFAs. I have a question where all the states in the DFA after reading that particular word from the alphabet will reach a particular state with ...
- 1