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

learn more… | top users | synonyms

2
votes
2answers
109 views

How to ensure the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$

Show that the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$ in the sense that, for every semigroup $S$ recognizing $X$, there exists a morphism from $S$ onto the syntactic ...
2
votes
2answers
311 views

Checking if the language is a regular one

Let A = $\{x \in \{a,b\}^{*} \mid |x|_{a} = |x|_{b} \}$. Is possible to find a regular expression $\alpha$ such that $L(\alpha)$ = A ? $L(\alpha)$ is the regular language defined by $\alpha$. It ...
0
votes
0answers
269 views

Deterministic Finite Automata: State Diagram Notation

Refer to the paper Radu Grosu, "Finite Automata as Time Invariant Linear Systems - Observability, Reachability and More". I have a problem understanding the state transition diagram of DMA $M_1$ in ...
4
votes
1answer
526 views

Drawing a PDA for a language

I am initiating myself into TOC and using sort of random resources from the web. I was looking at this problem from a Berkeley problem set: Construct a PDA to accept $$ L = {a^ib^j|i \neq j , 2i ...
2
votes
3answers
121 views

Regular Language

Prove that the language $\{a^{k} \mid k \equiv 0 \text{ or }k\equiv 2 \pmod 5\}$ is a regular language. I am just trying to figure this problem out for my own benefit. I am new to learning this ...
4
votes
1answer
123 views

Is $(p,\epsilon,p)$ a path of an automaton?

$A$ is an alphabet. An automaton over $A$ can be defined as a set $A_0 = (Q, E, I, T),$ where $Q$ is the set of states, $E \subseteq Q \times A \times Q$ is the set of edges or transition, $I, T ...
6
votes
1answer
302 views

Automata theory on infinite words: any video lectures?

I am fun of automata theory. Can you suggest good video lectures on the subject? (there is a good one here, but it is accessible from RWTH University only)
0
votes
1answer
60 views

Modelchecking on Automata, $\phi$ not SAT and $\phi \models$ False

Given a formula $\phi$ Is $\phi \models FALSE$ equivalent to $\phi$ not SAT? Or does $\phi \models FALSE$ means that $\phi$ is never $TRUE$ and $\phi$ not SAT means, that there existst at least one ...
0
votes
1answer
202 views

Proving that a grammar generates a language

Since every context free grammar is equivalent to a Push down automaton, to show that a grammar $G$ generates a language $L$, is it sufficient to draw a PDA equivalent to $G$ and then show the PDA ...
1
vote
3answers
265 views

Showing that two regular expressions represent complementary regular languages over {0,1}

How do up you show that two that the regular expressions, such as $(01+1)^*$ and $(0+1)^*\left(0 + 00(0+1)^*\right)$ represent complementary regular languages over $\{0,1\}$? I'm trying to do some ...
1
vote
2answers
64 views

Why this lemma is true?

Let $\Sigma$ be an alphabet of size $|\Sigma|=k$. Let $w\in\Sigma^*$ be a word over $\Sigma$. If $|w| > 2^k$, then $w$ contains an infix $y$ with $|y|\ge 2$, such that every letter occurring in y ...
5
votes
1answer
482 views

Connecting finite automata and regular languages in teaching/applications

I am considering giving a presentation to middle schoolers, aged about ten to fourteen, about finite automata and regular languages. Average American students have no problem with uses of the ...
1
vote
1answer
83 views

Show that $a^k w b^k$ when $|w|_a$ is divisible by $3$ is not regular

I want to show that $L = \{ a^k w b^k \mid k \geq 0, w \in \{a,b\}^*, |w|_a \text{is divisible by } 3 \}$ is not regular. I tried to use Pumping lemma as follows: Let $p$ be pumping length. $a^pb^p ...
0
votes
1answer
226 views

Properties of a valid DFA

Is a DFA required to have transitions on each input symbol from each state defined? If there isn't a path from state q1 to another state on input a for example, does that invalidate the DFA itself. ...
0
votes
1answer
228 views

How do I write this formally?

For every number N in a sequence of numbers it is true that each odd N is followed by 0 or more other numbers (not including 0) then the number N+1. How do I write this formally? This is my attempt ...
3
votes
1answer
836 views

If L is regular, so is $L-\{λ\}$?

A language is regular, by definition, if you can create a DFA for it. Then I need to prove that if $L$ is regular, then so is $L-\{\lambda\}$ for any $\lambda\in L$. Any ideas?
14
votes
1answer
404 views

Eilenberg's rational hierarchy of nonrational automata & languages

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised a Volume C dealing with "a hierarchy (called the rational ...
0
votes
1answer
132 views

Difference between $(a|b)^\ast$ and $a^\ast b^\ast$?

What is the difference between $(a|b)^\ast$ and $a^\ast b^\ast$? Can you show more examples of Kleene star and patterns and explain a little bit? I've searched so many sites in Google, but it returns ...
0
votes
1answer
287 views

Is it always possible to convert a non-deterministic PDA to a deterministic one?

Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
2
votes
1answer
516 views

Turing Machine Vs Linear Bounded Automata

Example of language accepted by Turing Machine but not by Linear Bounded Automata ? Is there any EXPSPACE language?
7
votes
2answers
411 views

A magic trick with synchronizing words

See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html Spoiler Alert Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
7
votes
2answers
194 views

Density of black cells in rule 110

Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell. Simulation of first 120000 ...
0
votes
1answer
68 views

How many neighbours should a cell have in a cellular automata?

So, I'm currently working with cellular automata but I started to wandered, what's the perfect amount of neighbours each cell should have if I'm working in a bi-dimensional space? Up to now I was ...
0
votes
3answers
178 views

Word problem in a free group

Can the word problem in a free group be solved by a finite state automaton? I know it can be solved by a pushdown automaton.
4
votes
1answer
133 views

Minimal DFA satisfying a finite view of a language.

Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq ...
1
vote
1answer
50 views

what is the effect of adding another stack to a PDA

does it increase the power of a push down automata? or does it have no effect on the power of the PDA ?
3
votes
2answers
450 views

Help in constructing a DFA equivalent to this NFA

First post here, woot. I've been a member of Stack Overflow for a while, so hopefully you guys are just as friendly! I'm having issues converting simple NFAs to DFAs... I just don't get it. ...
0
votes
2answers
423 views

String matching automata preprocessing

I have an alphabet A = {a,b,c} and a pattern P = "abcaab". The task is to build a finite automaton of the transition function (delta) for {0,6} (the length of the pattern) and each element of the ...
1
vote
2answers
69 views

Closure property of Alternating language

Problem Given a language $L$ is context-free, must $\operatorname{alt}(L)$ is also context free? where $$\operatorname{alt}(L) = a_1a_2a_3 \ldots, \quad L = a_1b_1a_2b_2a_3b_3 \ldots$$ I couldn't ...
1
vote
1answer
166 views

Finite Automata, basic question with semigroups

If we use the notation where when we say: $$M = M(G)$$ We mean to say that $M$ is a automata with states and alphabet elements of $G$. From here, I am posed this question (Abstract Algebra by ...
1
vote
1answer
780 views

Nondeterministic PDA to Deterministic PDA

Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
1
vote
1answer
172 views

CFG pumping lemma

I can't figure out how to prove this is a non CFG. $\{xy : x, y \in \{a,b\}^*, n_a(x) = n_a(y), n_b(x) = n_b(y) \}$, Where the number of a's in x = number of a's in y and number of b's in x = to the ...
0
votes
2answers
225 views

How can I prove that this language is regular?

Given a language $L$, define the language $K$ as the language $L$ where every second character is replaced with a $\#$. (Note: $\#$ is not part of the alphabet of $L$.) For example, if $L = \{ab, ...
0
votes
1answer
996 views

Extended transition function of a DFA - a proof

I would like to write a proof of the following statement $$ \delta^+(q,PQ) = \delta^+(\delta^+(q,P),Q) $$ $\delta^+$ - Extended transition function I have to do it by induction. However, I'm not ...
1
vote
2answers
537 views

NFA to DFA conversion, half the power set

Is there a way to tell when a NFA will use at least half the power set when converted to a DFA. I tried to create a few examples, but i just can't see a pattern that would say whether an NFA will use ...
0
votes
3answers
149 views

Having trouble with “languages”

Okay, so I come across a question: What language is represented by this regular expression: $$(((a*b)b) \cup b)$$ An example given prior to this is: L(anguage) = $\{w | w \in \{0,1\}\}$ L(anguage) ...
2
votes
1answer
655 views

Unable to construct Context-free Grammar from Pushdown Automaton

I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata. I can construct a CFG, but it ...
1
vote
1answer
115 views

What is this operation between sets {a, b}{c, d} do?

Not sure what this operation does, which is why i'm on here. It's not the cartesian product and no idea what it's called. I need to know to prove: For any language L, (Null set)L = L(null set) = ...
2
votes
3answers
277 views

What is the language of this DFA?

How would you write the language for this DFA as L(M) = {...}? I think in English I would say L(M) is defined as {a,b}* ending in b, ba or aa.
0
votes
2answers
122 views

How to represent a formal proof

I know how I want to do the proof, but I don't know how to represent it. It's an automata proof, so all I need to do is show that it is regular. How could I represent a DFA as a copy? So I have the ...
2
votes
1answer
483 views

Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$

Problem Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$ For the language $wcw^R$, it's much easier because the stack is always empty after ...
2
votes
2answers
2k views

Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$

Problem Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$ My initial idea was, If we read an $a$ push a $x$ onto stack If we read a $b$, there are two ...
4
votes
1answer
592 views

Question regarding stack operation notation in PDA

I'm currently reading two books: An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz. Introduction to the Theory of Computation, 2nd Edition by Michael Sipser. What ...
1
vote
1answer
196 views

Question regarding the initial stack symbol in Push Down Automaton

Let $L = \{a^nb^n : n \geq 0\} \cup \{a\}$, where $\Gamma = x, \$, \Sigma = {a, b}$, we have the NPDA of $L$ in three states: In the above state diagram, I can break the transtion $\lambda, \lambda ...
2
votes
2answers
156 views

Is it possible to prove that $L$ is a regular language?

Let $L = \{a^{f(m)} | m \geq 1 \}$ where $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ is monotonically increasing and complies that for all $n \in \mathbb{Z}^+$ there is $m \in \mathbb{Z}^+$ such that ...
3
votes
3answers
702 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
2
votes
4answers
10k views

Convert from DFA to NFA

For this language $\{ w | w \text{ contains at least three } 1's \}$, its DFA diagram is defined as follows: While trying to convert it to NFA, but I realized that its NFA would be identical to ...
2
votes
1answer
413 views

Understanding and using the transfer-matrix-method

Let $G = (V,E,\Phi)$ be a weighted directed graph and $\mathcal{W}' : E \rightarrow \mathbb{C}$ the weighting. Let additionally $m = \# V$, $E_m$ the $m \times m$ identity matrix. Let $v,w \in ...
4
votes
3answers
2k views

How to prove two regular expressions are identical in mathematical way?

I'm currently working on "regular expression" exercises in the textbook ("An Introduction to Formal Languages and Automata"), and the problem that I'm facing is, most of the time, my solution is ...
0
votes
2answers
700 views

Find the DFA for the language $L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$

Problem Find the DFA for the language $$L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$$ This is a problem from the book "An Introduction to Formal Languages amd Automata 4th edition", ...