Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
0
votes
2answers
39 views
regular expression
I would like to write the regular expression for the set of
all binary strings where
there are no three consecutive 0's.
The following strings are part of the language:
...
0
votes
2answers
34 views
Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.
Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.
It seems to use one Lemma: Pumping Lemma.
3
votes
2answers
133 views
Automata: 1=2, 2= 26, 3=1054, 4=5768, 5 =139314069504, 6 = ???
I am in my own Automaton (finite-state deterministic automata) research, so i have four sets of automata.
2 states automata,
3 states,
4 states and
5 states.
Input alphabet $\{0,1\}$
so...
the ...
0
votes
1answer
26 views
Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?
This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
2
votes
1answer
53 views
An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?
One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
1
vote
1answer
59 views
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $?
My attempt:
$G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of:
$$ S\to AbBC $$
$$A \to ...
1
vote
1answer
44 views
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?
How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?
I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
0
votes
0answers
14 views
Shortest trace for LTL
Given a finite trace semantics for LTL (one where u,i |= X phi does not hold if i = |u|) is there a better bound of the length of a minimal trace for a satisfiable formula ?
By better, I mean better ...
0
votes
0answers
128 views
Turing Machine question, this is NOT HW
I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
-1
votes
1answer
68 views
Decidability/Undecidability Question
Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability.
Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
2
votes
1answer
74 views
DFA worst case states
Suppose an NFA which accepts language of the form
L(N) = {w| w has 1 in n$^t$$^h$ from last symbol.}
Then the corresponding DFA would have 2$^n$ states(worst case of subset construction).
If we are to ...
1
vote
1answer
50 views
Proving Language accepted by DFA
I am stuck with a problem, as my proving skills aren't good(trying to improve).
Prob:
Given a State Table of DFA, decribe what language is accepted, and prove by induction it accepts that language, ...
0
votes
0answers
52 views
Pumping Lemma length, $K$ for context-free language
Please help me understand, and if possible, tips, to determine a pumping length $K$.
Suppose I have the example :
Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
0
votes
1answer
78 views
Decidability of a Turing machine always halting in at most ten steps
I've exam comping up soon and I need help with this. Consider the problem:
Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input.
Is this decidable? Prove your ...
0
votes
0answers
128 views
Turing Machine that accepts the language { www : w ∈ {a, b}*} [closed]
Turing Machine that accepts the language { www : w ∈ {a, b}*}
I'm trying to solve this but I'm not sure how to start! I understand how to solve it if it only has ...
2
votes
1answer
88 views
Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]
How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
2
votes
1answer
50 views
Constructing PDA with either one state or two states
If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
0
votes
1answer
171 views
Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.
I have exam coming up and I need help with this:
Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3
Thank you :)
2
votes
2answers
49 views
Giving a regular grammar for the language
I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
1
vote
2answers
57 views
Concatenation of 2 finite Automata
I have some problems understanding the algorithm of concatenation of two NFAs.
For example: How to concatenate A1 and A2?
A1:
...
1
vote
1answer
23 views
Can every regular language have a linear bounded automaton
As the question states:
I am trying to understand automata. Can every regular language have a linear bounded automaton?
2
votes
1answer
71 views
Is there a problem with this example?
In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
1
vote
4answers
78 views
Non-Deterministic Turing Machine Algorithm
I'm having trouble with this question:
Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language:
$$
L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, ...
0
votes
1answer
76 views
Turing Machine Variation
Hi i'm trying to figure out this question:
Give a formal definition of multihead-multitape
Turing machine. Then show how such a machine can be simulated by a standard Turing
machine
Can someone ...
1
vote
2answers
91 views
Finite automaton that recognizes the empty language $\emptyset$
Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
2
votes
2answers
62 views
Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.
I'm having my exam in few days and I would like help with this
Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
4
votes
2answers
119 views
Push down automata problem
Informally describe the Nondeterministic PDA that generates:
$$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$
My initial plan was to use nondeterminism to go through each character before ...
0
votes
1answer
35 views
Automata: Proof
Here is the problem:
Consider a NFA, M = (K, Σ, Δ, s, F) with (p, a, q) ∈ Δ. Prove that (pʹ, aw) ⊢∗ (qʹ, w) for any w ∈ Σ∗, q′ ∈ E(q) and p′ with p ∈ E(p′).
Thanks in advance.
5
votes
0answers
176 views
What is the class of languages accepted by DFAs whose transition monoids are transitive permutation groups?
In the Wiki page
A permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. ..... A formal language is p-regular ...
1
vote
1answer
97 views
If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular
Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language.
I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
2
votes
2answers
76 views
Is this proof using the pumping lemma correct?
I have this proof and it goes like this:
We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$.
Then, the following proof is given:
There is a $p$ ...
1
vote
1answer
87 views
Regular Languages Algorithm?
I need help proving the following question:
Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length.
So far, I know ...
3
votes
1answer
113 views
Context Free Language? Proving through grammar?
I need help solving this question:
Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language?
That is the number of $a$'s equal the number of $b$'s equal twice the ...
3
votes
2answers
43 views
If $L\in REG$ then $M$ has a finite number of distinct rows
Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$:
$$
m_{x,y}=\begin{cases}
1 & x y\in L\\
0 ...
0
votes
1answer
29 views
Questions about DFA with Sigma* exiting arrow and RE
Assume Sigma* contains all english alphabet chars. Then in my DFA, I have an exiting arrow of Sigma* and another exiting arrow of "a"(symbol from the alphabet) from one state. Will this be a valid ...
0
votes
1answer
124 views
An infinite context free language can be split into two infinite regular languages
Prove or disprove
Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
-1
votes
2answers
65 views
Is λ={λ} true or not
I know that λ={λ} is true i want to know How can i prove that λ={λ} is true or not?
Thanks in advance.
0
votes
3answers
70 views
Is indistinguishability an equivalence relation?
Let x and y be strings and let L be any language. We say that x and y
are distinguishable by L if some string z exists whereby exactly one
of the strings xz and yz is a member of L; otherwise, ...
2
votes
1answer
104 views
Would the following NFA accept all strings?
The question asks the following: "Let N be a nondeterministic finite automaton with s states. Suppose than N accepts all strings of length s or
less. Does it follow that N accepts all strings? (If so, ...
1
vote
1answer
88 views
How would I go about proving for this NFA?
I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following:
N accepts the string x if the number of distinct ...
3
votes
2answers
187 views
Question about regular languages and finite automata
We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
0
votes
1answer
33 views
How can I prove a DFA accepts a certain mininum number of states?
We know that if there are two languages, L1 and L2, if L1 and L2 are regular, the intersection of those two is also regular. Suppose we have two machines, M1 and M2, and using them, a new machine M3 ...
1
vote
2answers
50 views
Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?
DFA
Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$?
For part 2, wouldn't it require M states if the word length is M?
1
vote
1answer
113 views
Finite state machine to report when the last 4 inputs were 1011
Suppose you want to construct an FSM containing one input and one output. Consider the example: The machine should assert the input (set to 1) when the last four bits taken in as input match the ...
1
vote
2answers
119 views
suffix regular language
Can someone give me an idea how to prove this:
suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...
1
vote
2answers
55 views
Proving this language is regular?
Is $$L =\big\{x^ny^m : |n-m| = 2\big\}$$ a regular language?
I can't seem to figure this question out, and i've tried drawing a dfa but I still can't seem to find it. If there is a possible dfa, ...
1
vote
3answers
62 views
regular language?
I need help proving whether this language is regular or not.
$$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$
That is, the number of $a$'s is even and the ...
2
votes
1answer
152 views
How to construct a grammar $G$ such that $L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\} $?
Construct a grammar $G$ such that $$L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\}$$
My attempt:
I first constructed a grammar for the langugage $L(G_1) = \{ a^nb^m|n = 2m,m,n \ge = 0\}$,
$G_1 = (\{ S\}, ...
0
votes
2answers
54 views
What are the states of this NFA?
I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states:
$q_0$: the string ends with bb.
...
0
votes
1answer
32 views
Büchi Pushdown System Accepting Run
From the following definitions:
Definition (Büchi Pushdown System)
A Buchi pushdown system (BPDS) is a tuple BP = (Q,S,→,Qf) with (Q,S,→) a PDS (where S is the stack content) and Qf ⊆ Q a set of fi ...
