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

learn more… | top users | synonyms

1
vote
1answer
54 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
1
vote
2answers
69 views

New automaton that runs two others step by step?

If I have two automatons for two languages ($M_1, M_2, L_1,L_2$ respectively), what would be the procedure to mix them by defining a new automaton such that the new automaton would accept the words ...
1
vote
2answers
156 views

Whether $L=\{(a^m,a^n)\}^*$ is regular or not?

I am condidering the automatic structure for Baumslag-Solitar semigroups. And I have a question. For any $m,n \in Z$, whether the set $L=\{(a^m,a^n)\}^*$ is regular or not. Here a set is regular means ...
1
vote
1answer
386 views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...
1
vote
2answers
421 views

Showing that a language is regular - Pushdown Automaton

So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.
1
vote
2answers
94 views

Solve right linear set equations

Trying to solve this set of equations. I'm feeling like I'm making it so complicated. Of course + is union. Am I on the right track? A = 0B + 1D B = 0C + 1A C = 0A + 1B + λ D = OD + 1C + λ A ...
1
vote
2answers
385 views

Can _any_ NFA be converted to a DFA?

I was wondering if for every NFA there exists an equivalent DFA? I think the answer is yes. How would one prove it? Since I'm just starting up learning about Automata I'm not confused about this and ...
1
vote
2answers
168 views

Pushdown Automaton

Can someone help me construct a pushdown automaton to recognize the following regular expression representing the language $(a^3+a^5)$* using as few states as possible? How can this be done using a ...
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 ...
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 ?
1
vote
1answer
167 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
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 ...
1
vote
1answer
72 views

$NP^{PP} vs. PP^{NP}$, which one subsumes the other?

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ...
1
vote
2answers
31 views

NFA for $L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}$

Write an NFA to recognize the language $$L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}.$$ I'm not quite sure how to do this question. I don't know how to keep ...
1
vote
2answers
30 views

Is this DFA correct?

I am reviewing. I need to write a DFA that accepts a string w such that bab is not a substring. Is there any error. Also, any guideline or tips? Since it's a DFA I don't make more than 2 ...
1
vote
2answers
95 views

Euclid's Proof that there are an infinite number of primes

I'm trying to clarify my understanding of decidability of a language. The following question is totally made up by me so I hope it makes sense. Let $L = \{A: A \text{ is an algorithm that can ...
1
vote
1answer
21 views

How to prove the following related with regular languages

How can we prove the following. If $$\sum$$ is any alphabet and L is any language $$L \subset \sum*$$ Then L*L* = L* ?
1
vote
1answer
38 views

Particular Problem for Context Free Grammars

Consider the context-free-grammar $G$ defined by productions: $$ S \rightarrow aS\,|\,Sb\,|\,a\,| b $$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. I ...
1
vote
1answer
26 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
1
vote
1answer
25 views

Showing that all regular languages are closed under reversal

I'm trying to show that $L^{reverse} = \{w^{reverse}:w \in L\}$ is a regular language. The first argument I can come up with is simply: if we have an NFA for $L$, then an NFA for $L^{reverse}$ can be ...
1
vote
1answer
126 views

Languages and Grammar (Finding a language)

I have a trivial question (that I have actually solved, hopefully) although I am a bit curious if my result is alright. We have $N= \{S , C ,D\}$, $T=\{c, d\}$ and $P = \{S \to Dc, D \to Dd, D \to ...
1
vote
1answer
53 views

About described DFA

I need to find DFA (or NFA, $\epsilon$-NFA, it's not improtant (I know how to convert between them)) that accept all strings of $0$'s and $1$'s such that every block of five consecutive symbols ...
1
vote
2answers
50 views

If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$?

Given the words $v,w \in \sum^*$, is this correct? If $v^6w^8 = w^{12}v^4$ then $(vw)^2 = v^2w^2$ If $vw^2 = wv^2$ then $v=w$ For one, I tried $v=\epsilon, w=\epsilon$ and it worked, and ...
1
vote
3answers
64 views

Why is this the $L(M)$ of this DFA?

Why is this the $L(M)$ of this DFA? Can someone please explain it? I am new to this course. When I tried alone answering the question of "What is special about the words that get accepted by this ...
1
vote
1answer
33 views

Post-concatenation of the languages represented by the null set

I have a small question regarding concatenation of regular languages: Is it true that the concatenation $L\varnothing$, where $L$ is any regular language, result in $\varnothing$? Namely, does ...
1
vote
1answer
72 views

Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
1
vote
1answer
44 views

Stochastic Automaton accepting every word with same probability

I am looking for a stochastic automaton, which induces the same probability $c \in [0,1]$ for all words in $\Sigma^*$, where $\Sigma$ is some finite alphabet. A stochastic automaton over an alphabet ...
1
vote
1answer
85 views

Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
1
vote
1answer
113 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
2answers
72 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
93 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 ...
1
vote
2answers
627 views

How to prove by pumping lemma these languages are not regular?

$L_1 = (a^k * b^r \mid k \neq r^2)$ $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
1
vote
1answer
311 views

Show that every finite automaton is a one-state pushdown automaton

I'm reading a book that states: Every finite automaton is a one-state push-down automaton How can I go about proving it?
1
vote
2answers
97 views

Pushdown automata - definition and definition of $\vdash$

I am reading about pushdown automata and I don't understand the definition of $\vdash$. My book writes that $$(q,aw,Z\alpha)\vdash(p,w,\beta\alpha)$$ if $$(p,\beta)\in\delta(q,a,Z)$$ Can someone ...
1
vote
1answer
150 views

Which automata recognise the algebraic numbers?

I am reading historical stuff on the algebraic and transcendental numbers. Descartes, in his Geometry, excluded all curves not expressible as algebraic equations. Later, Leibniz called such curves ...
1
vote
3answers
266 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
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
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 ...
1
vote
1answer
66 views

Turing machine for the language a^nb ^2nc^3n

How can we give a Turing Machines that accept following language. $$a^nb^{2n}c^{3n}$$ I am allowed to use also pseudo-code descriptions (i.e. high level descriptions of movements of r/w head):
1
vote
1answer
35 views

Deterministic Push-Down Automata

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$
1
vote
1answer
70 views

An algorithm that minimises the number of states for a conversion from a DFA to an NFA

I am looking for an algorithm that can convert from a DFA to an NFA, while at the same time producing the minimum number of states for the NFA. My gut tells me this can be done with around $n$ ...
1
vote
1answer
29 views

having hard time reading symbols in this Turing Machine

I am reading few books and I am looking at different examples of a Turing Machine, and I am getting frustrated reading symbols especially in this example...What does ...
1
vote
3answers
86 views

Draw a finite state machine which will accept the regular expression $(a^2)^* + (b^3)^*$

Draw a finite state machine which will accept the regular expression: $(a^2)^* + (b^3)^*$ In particular, I am confused by the $+$ sign, what does it exactly mean? Most literature I could find about ...
1
vote
1answer
38 views

Constructing PDA for a language

I want to prove or disprove that for a given two PDA's (Pushdown Automata) $M_1$ and $M_2$, we can build a PDA $M$ such that $$L(M) = \{w \in L(M_1) \mid w\text{ contains some string in ...
1
vote
1answer
32 views

Is there a prefix-free regular language whose set of proper prefixes is not regular

Is there a regular language $L$ such that the language $$L^\prime := \{ w : w\text{ is a proper prefix of a word in }L \}$$ has the following properties: $L^\prime$ is not regular, and $L^\prime$ ...
1
vote
1answer
55 views

Prove or disprove whether the following is a regular language

I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ...
1
vote
1answer
44 views

Checking some Regular Expression problems

I'm given the alphabet $$ \Sigma = {\{a,b}\} $$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ...
1
vote
1answer
53 views

How to construct a grammar G such that L(G)={x^ny^mx^my^n/m,n>1}?

construct a grammar $G$ such that $L(G)=\{x^ny^mx^my^n/m,n>1\}$? I don't have much idea how to approach this one. Could some help me to understand how to approach these kinds of problem?
1
vote
1answer
54 views

Is the PDA I drew correct?

Could you tell me if the language $L=\{a^{m}b^{n}:m \neq n,m>0,n>0 \} $ is accepted by the following pushdown automaton, where the alphabet of the stack is $\{a,z\}$ and $z$ is the initial ...
1
vote
1answer
49 views

is this language regular or not?

I have problem with this language $$L = \{ a^n b^m : \text{$n+m$ is odd} \}$$ is it regular or not My Solution I used pumping lemma, w = a^2p b^2p+1 (the same for a^2p+1 b^2m ) ...