Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

7
votes
0answers
243 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 ...
3
votes
0answers
1k views

My Moore and Mealy machines look the same. Why?

For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with ...
2
votes
0answers
56 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
2
votes
0answers
50 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
2
votes
0answers
30 views

halting problem

Prove that it is undecidable for the halting problem of a deterministic Turing machine which accepts nonrecursive language or in-other-words: let's say we have a deterministic Turing machine which ...
2
votes
0answers
50 views

Blanks in the Tape of a Turing Machine

I used to have a lot of trouble with Turing Machines, primarily because I thought that in-between input symbols on the tape, one could have an arbitrary number of blanks, so every input would need to ...
2
votes
0answers
25 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
2
votes
0answers
47 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
47 views

Quality of Reduction of finite automata

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a ...
1
vote
0answers
28 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
0answers
18 views

Can the NFA constructs be minimized?

When converting a regular expression to a NFA you need to use certain constructs. My question is can these constructs be minimized? We have one with 4 states, I want to use the one with 2 states ...
1
vote
0answers
46 views

Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
1
vote
0answers
42 views

Extended PDA vs TM

We studied in class that PDA is less powerful than TM. My question is: Extended PDA : for every $\alpha,\beta \in \Gamma \cup \{\epsilon\}$, $\sigma \in \Sigma \cup \{\epsilon\}$, $q,r \in Q$, $w ...
1
vote
0answers
41 views

Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...
1
vote
0answers
78 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
1
vote
0answers
47 views

CERNY CONJECTURE ,reset sequence

given a reset/synchronizing sequence $w\in \Sigma^*$ ( w is a word in the input alphabet of the DFA which sends any state of the DFA to one and the same state), prove for an automata with k states ...
1
vote
0answers
45 views

Turing Machines

Suppose that $\Sigma$ is a finite set and that $L_1$, $L_2$ and $L_3$ are Turing acceptable subsets of $\Sigma^*$ that satisfy the following properties: $L_1 \cup L_2 \cup L_3 = \Sigma^*$; $L_1 \cap ...
1
vote
0answers
45 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
1
vote
0answers
73 views

Constructing an NFA accepted by a grammar

Contruct an NFA of the language accepted by the grammar below. $$G=(\{S,A,B\}, \{a,b,c\},S,P)$$ $P: S\rightarrow abaS\ \ | \ cA\\ \ \ \ \ \ \ A\rightarrow bA\ \ | \ cB \ \ | \ aa\\ \ \ \ \ \ ...
1
vote
0answers
18 views

Given two minimal FSMs with one accepting a subset of the other, must a simulation exist?

As part of an example, Abstract and Concrete Categories, section 3.35, claims: For every two minimal [by number of states] $\Sigma$-acceptors $A$ and $A'$, there exists at most one simulation $A ...
1
vote
0answers
134 views

Draw the state diagrams for the PDAs

Give informal English descriptions of PDAs for the languages and draw the state diagrams for the PDAs. The complement of the language $ [a^nb^n| n ≥ 0] $ My informal description: The PDA uses it's ...
1
vote
0answers
127 views

PDA state diagram with an inifinite languge but with no looping states

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
1
vote
0answers
102 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
0answers
158 views

Confusion related to state equivalence of finite state machines

I have this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input ...
0
votes
0answers
8 views

Is the language $L = \{0^m1^n: m \neq n \}$ not context free?

I have been trying to prove that this is not a context free language using the pumping lemma for CFLs. I have tried for hours but am not able to prove it. Is it a context free language or not? How to ...
0
votes
0answers
6 views

DFA : if W ϵ {a,b,c}* (|w|a-|w|b+c) mod 3>=1

can you help me to solve this problem ? this is my homework and unfortunately i can't solve it , How can i design a dfa for this question ? L={ W ϵ {a,b,c}* (|w|a-|w|b+c) mod 3>=1} . . [a , b , c are ...
0
votes
0answers
27 views

Context-free languages

Is the following language context-free? $\{ w \in \{a,b,c\}^* : (\#_a(w) - \#_b(w)) \cdot \#_c(w) = \#_b(w)$ and all c's are encountered before any a$\}$. $\#_a(w)$ = amount of a's in w Thanks in ...
0
votes
0answers
8 views

how to convert Finite Automata into Push Down Automata

I am trying to convert Finite Automata into Push Down Automata and I am not sure if I am doing this right. There are not many good tutorials on this topic that I can find, but this is what I have. I ...
0
votes
0answers
10 views

Cartesian product of a DFA and PDA

I am just wondering how to do it. I am not quite sure if this is the right way. 1) Write down all the combination of states. 2) Take into consideration the "input" side of the DFA and write the ...
0
votes
0answers
15 views

Designing a pushdown automata

I think I realized something, but I am not sure. So what I think I've realized is that if you have to design a L such that it accepts any string with the same amount of 1 and 0. You need 2 states: ...
0
votes
0answers
34 views

Is this grammar ambiguous?

$S > SS|10|0$ $S > SS > SSS > 0SS > 00S > 000$ $S > SS > 0S > 0SS > 00S > 000$ $2$ leftmost derivations
0
votes
0answers
12 views

Conversion from PDA to CFG

We have the pushdown automata (q) -> a,X/Y1 Y2 Y3 -> (r). and the template for it is [qXx] -> a[rY1y][yY2z][zY3x]. our teacher used another template that was derived from the first one. ...
0
votes
0answers
15 views

Relationship between pushdown automata and CFG

I thought that pushdown automata and CFG were separate things in that one was the graphical expression of the other, but I saw a pushdown automata that uses CFG terms such as epsilon, S, S->1S0, or ...
0
votes
0answers
52 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
0
votes
0answers
119 views

Up-Down Automaton

I've been give this question, about Pushdown Automata. they defined a new Automata, up down automata, as followed- it has all options a regular Automata has, but : and for each: now I need to ...
0
votes
0answers
25 views

Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$?

Let $L_1,L_2,L_3$ be languages, Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$? After a half an hour of trying to disprove it, I've decided my intuition might be wrong. ...
0
votes
0answers
31 views

Context-sensitive grammar for this language

In order to write a context-sensitive grammar for: $L = \{ a^{n} b^{n} c^{n} d^{n} : n \ge 1 \}$ One possible set of productions is: $S \rightarrow aBCd | abcd $ $aB \rightarrow aaBb | ab | ...
0
votes
0answers
30 views

Is this a context-free language?

Let $L = L_1^* \circ L_2^*$ where $L_1 = \{1^n 0^m 1^n : n,m \in \Bbb N\}$ and $L_2 = \{0^m 1^{2m} : m \in N\}$. Is the language $L$ a context free language? I think I can write automata for $L_1$ ...
0
votes
0answers
26 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
0
votes
0answers
54 views

Converting a DFA to an NFA: Start State

When we try convert some NFA $N = (Q_N,\Sigma,\delta_N,q_0,F_N)$ to a DFA $D = (Q_D,\Sigma,\delta_D,\{q_0\}, F_D)$, why is it that $q_0$ becomes $\{q_0\}$? (Where $q_0$ is a single start state, ...
0
votes
0answers
65 views

Formal Languages: String Notation

In formal languages, we usually denote an alphabet $\Sigma$ as the set of symbols it contains, e.g. $\Sigma = \{0,1\}$ is the binary alphabet. It can be confusing because we denote $\Sigma^1$, the ...
0
votes
0answers
25 views

CF grammars and productions that are not CF

I'm learning about CF (context-free) grammars and I thought I understood what CF meant but I want to make sure I'm getting this concept. So I'm using some examples to make sure I'm understanding: $S ...
0
votes
0answers
36 views

Homework problem with expressions.

I am doing homework and I have multiple choice question that states which are the valid expressions. $bb \Phi a^*$ $(aa)^+ b(a+b)^*$ $\Phi (a+b+c)^*$ $ba^nbb: n>0$ $\lambda (a+b)^*a(bb+a)$ ...
0
votes
0answers
30 views

how to create a automata for a discrete Duration Calculus

can someone explain, how to create a time-automatathat accept the language? $$ \mathcal{L}(\diamond(l=1) ) $$ I don't know how to realize the diamond-operator //UPDATE the lozenge is the diamond ...
0
votes
0answers
58 views

Binary regular language?

Given $m,n∈Z$, $A=\{a,b,c\}$ is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this binary language $L$ regular over $A(2,\$)$ ( i.e.$\{A∪\{\$\}\}\times ...
0
votes
0answers
41 views

Regular language?

Is the binary language $L=\{(a^2,a)\}^*=\{(a^2,a),(a^4,a^2),(a^6,a^3)...\}$(a subset of $A^*\times A^*$,with $A=\{a,b,c\}$ a finite alphabet set) is regular over $\{A∪\{\$\}\}\times ...
0
votes
0answers
24 views

Limit of NFA for recognizing language restricted by length

Let $L$ be a language over the alphabet $\Sigma=\{0,1\}$ where all words in $L$ have at most 8 symbols. Note each language $L$ satisfying this restriction can be recognized by a DFA with at ...
0
votes
0answers
29 views

How do you define summary and extension of weighted finite state transducers?

So reading through this paper: http://www.cs.nyu.edu/~mohri/pub/fla.pdf I see that a weighted finite state transducer (WFST) is a semiring, and many operations on WFST can be expressed in terms of ...
0
votes
0answers
17 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
247 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 ...