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

learn more… | top users | synonyms

1
vote
1answer
37 views

Write grammar for given language

I'm trying to write a grammar for the language below: $$(a+b)^*−\{𝑤𝑤𝑤 ∶ 𝑤\in\{a,b\}^*\}$$ could anyone help me?
1
vote
2answers
54 views

What the way studying math to automata theory

Good day everyone. I need to know automata theory. Can you advice me the best way to study math? What themes will I need to know to understand automata theory. What a sequence of study? What level ...
1
vote
1answer
11 views

Find a state machine or a regex that accept the following language description

The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ...
1
vote
1answer
86 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
50 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
53 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
108 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
25 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
41 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
31 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
466 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
70 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
54 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
70 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
39 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
117 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
432 views

Does closure under the union and concatenation operations imply closure under the star operation?

Given any two languages $A$ and $B$, recall the following regular operations: Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Concatenation: $A \circ B = \{xy \mid x \in A \text{ ...
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
103 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
117 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
83 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
98 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
750 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
390 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
103 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
161 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
306 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
226 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
42 views

NFA (nondeterministic finite automaton) made out of the Bible?

Let B be the language over alphabet {a, ... z} consisting of those words occuring in the Bible. Thus, B = {in,the,beginning,god,created,...}. Describe an NFA whose language is B. Describe what ...
1
vote
1answer
25 views

what do we mean by saying that a particular computing machine is more powerful than another computing machine?

I am having confusion in understanding the concept of the word "powerful" in automata theory. Even the confusion arises that if I have a DFA with single final state ,so then is it more or less ...
1
vote
1answer
45 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
1
vote
2answers
27 views

How to construct the DFA for the following question?

Given $L=\{ab^5 w b^4 \}$ where $w=\{a,b\}^*$. I am not able to construct it, I tried it but getting problems with the transitions for input symbol a.
1
vote
1answer
20 views

Two DFA to one NFA.

Let assume that I have given DFA $D$ which recognize language $L$. Now I would like create the DFA/NFA which recognize the language $L'$. $$ L' = \{ w \in L : |w| = 2k, k \ge 0 \}$$ In words, $L'$ ...
1
vote
2answers
32 views

Convert NFA to DFA

I have to convert the following NFA's into the equivalent DFA's. I have done the following: Could you tell me if it is correct??
1
vote
1answer
33 views

Show that the language is regular - Closure

For languages $A$ and $B$, let the perfect shuffle of $A$ and $B$ be the language $$L=\{w \ \mid \ w=a_1 b_1 \dots a_k b_k, \text{ where } a_1 \cdots a_k \in A \text{ and } b_1 \cdots b_k \in B, ...
1
vote
1answer
21 views

Language described by inverting accepting states of NFA

What is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states. Is there a ...
1
vote
2answers
36 views

NFA construction problem

I need to construct an automaton that recognizes the following language of strings over the alphabet $\{a,b\}$: The set of all strings over alphabet $\{a,b\}$ with the subsequence $abba$. (A ...
1
vote
1answer
76 views

Context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, S -> AB | c A -> aAb | c B -> bBa | c Now correct me if I'm wrong, but if this language has an NFA it ...
1
vote
1answer
58 views

Proving languages are undecidable

Let L5 be the language { {G,D} | G is a CFG, D is a DFA, and L(D) ⊆ L(G) } Show that L5 is undecidable. Is L5 R.E.? Is it co-R.E.? I am not quite sure where exactly to start with this. Could ...
1
vote
1answer
60 views

Can 2 items be added/taken away from a stack in push down automata at once?

Here is a language and 2 ways (I hope) of representing it with a PDA. Can I use the notation (b,a $\to$ ee) or anything of the like, to take away 2 items from the top of a list at once? Such as I ...
1
vote
1answer
46 views

Automata Language regularity proof by construction.

I've been trying to prove or disprove a question that popped during our last session in Uni, we've been using automaton constructing to prove regularity for a while now and I really do have the handle ...
1
vote
2answers
84 views

Divisibility problem using DFA

Original problem: Create a DFA for every positive integer $k$, so that when DFA takes a binary string (reading from most significant bit), decides whether the number is divisible by $k$. A DFA for a ...
1
vote
1answer
30 views

Is it possible to build an Pushdown Automata for an Ambiguous Context-Free Grammar?

Say I have the following grammar: $$S \to \epsilon \mid [S] \mid (S) \mid SS$$ This grammar is ambiguous as both the following parse trees yield the empty string $$S \to \epsilon$$ $$S \to SS \to ...
1
vote
1answer
27 views

Show a Turing Machine accepts all DFAs

You have a Turing Machine $T = \{ \{ A \} \mid A$ is a DFA and $L(A) = \Sigma^* \}$ i.e. the DFA that accepts all languages. Show it's decidable. Can you use the complement of this, the DFA that ...
1
vote
1answer
32 views

Checking correctness of finite state automata designed

How to check correctness of finite state automata we have designed for a regular expression with the help of any computer program or prolog?
1
vote
1answer
211 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
66 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
116 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
45 views

Checking my CFG to CNF answer

I attempted to transform the given CFG into CNF. $$S → ASA|A$$ $$A→aa|ε$$ Here are my steps: $$S→X$$ $$X→XA|AX|A$$ $$A→aa$$ $$S→X$$ $$X→XA|AX|YY$$ $$A→YY$$ $$Y→a$$ $$S→XA|AX|YY$$ ...