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

learn more… | top users | synonyms

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
666 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
285 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
123 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
486 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
600 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
198 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
157 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
714 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
419 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
721 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", ...
4
votes
3answers
898 views

How to compute the transition function in non-determinism finite accepter NFA?

I'm currently teaching myself Automaton using Peter Linz book - An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51): ...
1
vote
1answer
845 views

Proving regular expressions to be equivalent

I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof). The process is to show that R1 is a subset of R2, and ...
0
votes
1answer
249 views

Complementary language of a context free grammar

First post on Mathematics ;) I'm stucked with a problem related to automata theory / formal grammars. The problem ask the student to design a Pushdown automaton that accepts the complementary ...
2
votes
1answer
213 views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
4
votes
1answer
77 views

Enhancing the monoid structure over a finite alphabet to prove Arden's rule

Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the ...
3
votes
1answer
2k views

How to show that $ALL_{DFA}$ is in P

How can I show that $ALL_{DFA}$ is in P ? $ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
1
vote
2answers
265 views

Is this DFA correct

I'm supposed to construct a DFA which accepts { w | w is a word except 'aa' and 'aaa' } Is this the correct solution? The thick line state is supposed to be the end state. EDIT Sry, somehow ...
1
vote
2answers
3k views

Understanding $\epsilon$ transitions in a finite state automaton

I am trying to understand how $\epsilon$ transitions work. From what I've read, when you "go" to a state S that has arrows pointing outwards with $\epsilon$'s in it, you automatically go to those ...
2
votes
1answer
806 views

Nondeterministic Finite Automata to Deterministic Finite Automata?

I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
2
votes
5answers
5k views

Program for working with DFA/NFA/PDA?

I'm looking for a program or utility to help construct DFA/NFA/PDA etc. and the like. The main reason I'm interested in this, is because I want to be able to move the various states around without ...