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

learn more… | top users | synonyms

2
votes
1answer
61 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
0
votes
2answers
110 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
1
vote
1answer
31 views

context free grammar that describes even numbers

I am learning about context-free grammars and as a toy example I wanted to design one that describes binary digits ending with 0. My attempt : S -> 1S | 0S | e0 - where e is the empty string. Is this ...
-1
votes
1answer
71 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
0
votes
1answer
49 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
2
votes
0answers
38 views

Lattice worms with nontrivial deaths

In Paterson's worms, a triangular lattice is used. A worm can move in 6 directions. As each node is hit, the worm follows an internal rule for which edge it will eat next based on the edges already ...
1
vote
1answer
59 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
0
votes
1answer
48 views

A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
0
votes
1answer
70 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
0
votes
1answer
29 views

Algorithm that takes input desc. of two PDAs and outputs intersection of langs. recognized by two PDAs

Does there exist an algorithm which takes as input the descriptions of two pushdown automata, $P1$ and $P2$, and prints the description of another pushdown automaton which recognizes the intersection ...
0
votes
1answer
25 views

Deciding TM which fails to halt whenever the length of its input string is a prime number

I have the following Statement: "A TM called $A$ which fails to halt (i.e runs forever) whenever the length of its input string is a prime number, and eventually halts for all other input strings" ...
-1
votes
1answer
57 views

disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
1
vote
1answer
207 views

Complex automata Rubiks cube question (with picture) help needed

Question 1 A Rubik’s Cube is a puzzle in the shape of a cube. Each face is covered by nine stickers, each of which is coloured with one of six colours: white, red, blue, orange, green, andyellow. An ...
0
votes
0answers
29 views

Design an finite automata for 010 and 01? [duplicate]

I have tried below question for designing automata but didn't success . ...
1
vote
1answer
90 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 ...
3
votes
1answer
101 views

Exponential objects in a category of abstract automata.

I'm working with a more or less standard definition of the category Aut(C) of automata over a category C (where C has finite products) which has tuples $$ A=\langle I_{A},O_{A},S_{A},\sigma_{A}, ...
0
votes
0answers
182 views

How to check whether a language is regular or not?

Say I have a given expression like $L_1\{a^n\mid n\ge0\}$ $L_2\{b^n\mid n\ge 0\}$ Then what is the procedure of checking weather L1.L2 is regular or not?
0
votes
1answer
35 views

How does the push-down automaton have to look like?

Could you give me a hint how to find a push-down automaton for the language: $$L=\{ a^n b^{2n} | n \in \mathbb{N}\}$$ How does the push-down automaton have to look like?
1
vote
2answers
51 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
1answer
338 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
74 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}$$
2
votes
1answer
29 views

Stack automata with nonequality

I encontered the following problem that I'm unable to solve. The goal is to construct a stack automata, that accepts language $$ L = \left\{u\mathrm{\underline{c}}v \mid u,v \in ...
4
votes
2answers
63 views

Turing Machine Decidability

I have been working on this problem for few hours, but haven't been able to come up with a solution : Is the following problem decidable? Given a TM M, whether there is a w such that M enters each of ...
1
vote
1answer
153 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
2answers
801 views

pumping lemma: ww^R not regular

I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma. Let $p$ be the pumping length and $s = a^pbba^p$. $x = \epsilon$, $y = ...
1
vote
1answer
57 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$$ ...
1
vote
0answers
73 views

Create a finite-state machine

I need to create a finite-state machine which accepts strings whose characters are in {a,b,c} and produce output strings of T's and F's. The machine outputs a T once the characters ab is encountered ...
0
votes
2answers
49 views

minimal DFA with four states

I want to minimal this DFA: But i don't know what to do. Anyone can help me? Thanks
1
vote
0answers
103 views

Proving context free language membership is $P$ complete with respect to log-space reductions

This is exercise from Introduction to Automata theory, Languages and Computation, by Hopcrof, Ullman (first edition). I found example of polynomial reduction to some problems in logic, or graph ...
2
votes
1answer
50 views

Decide whether DFA accepts all Strings

Wikipedia : Because DFAs can be reduced to a canonical form (minimal DFAs), there are also efficient algorithms to determine: whether a DFA accepts any strings. whether a DFA accepts all strings. ...
2
votes
1answer
137 views

Can you draw the e-NFA from the following definition?

I am trying to understand the solution, because I think I got it completely wrong. I wrote we could take the initial DFA and replace the normal transitions with epsilon transition except for all ...
0
votes
2answers
34 views

Is there a fast way to know whether a language is regular or not?

Or at least have an idea? Because I can't see whether a language is regular before I can disprove it by pumping lemma and it takes me like a hour to try to disprove.
0
votes
1answer
75 views

What did the proof by diagonalization actually disprove?

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fourse5.html I sort of understand the proof, but is it showing that some language are undecidable? If so, what language exactly? Because each ...
0
votes
1answer
155 views

Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
0
votes
1answer
85 views

turing machine accept and reject state

I am pretty new to Turing Machines and I am trying to understand the basic things first...so my question is , would this machine accept all words ending in 'a' ? if ...
1
vote
2answers
29 views

Regular expression translation.

Given a set {1,2,...9} how can I construct a regular expression starts with a 3 has no 8's and has even number of 6's? Here's what I tried: $$$$ Define a new set no8 = {1,2,3,4,5,6,7,9} ...
1
vote
1answer
49 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 ...
0
votes
0answers
63 views

how do I make this post machine accept aab or baa?

so far I made it accept, a, aaa,bab but now I want strings aab or baa. How would I do this ? this is what I have so far... edit: @Hagen von Eitzen here is the example of Post Machine that a lot of ...
0
votes
0answers
66 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 ...
2
votes
2answers
47 views

Regular Expressions Help [duplicate]

I need a little help with Regular Expressions. The allowed operations are obviously + (union) , * (Kleene star) and concatenation. I have to write Regex for the following 2 examples. I have tried a ...
0
votes
2answers
59 views

DFA Construction with three strings in language

Draw DFA that recognizes the following language, with the alphabet {0, 1} {0011, 11, 0101} I'm having a lot of trouble with this, because I know DFA have to have a determined path from each state ...
0
votes
1answer
98 views

What does q-prime ($q'$) actually mean?

I'm learning about finite automata right now, and struggling with a bit of the math notation. In the explanation here: http://math.stackexchange.com/a/563875/125649, the user explains that the ...
1
vote
2answers
57 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
61 views

How to construct NFAs that recognize the following languages.

I am new to this computation theory and I am trying to answer the following question. Can you please check if I am on the right track? If there is any material that I can study for problems like ...
1
vote
2answers
110 views

Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
1
vote
3answers
216 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
3answers
125 views

Reducing a Decidability Problem to the Halting Problem

Let $L = \{(M, n): M$ halts on less than $n$ elements from a set S $\}$ I'm trying to come up with a generalization on how to solve these types of problems so I have not defined what S is. Since the ...
-1
votes
1answer
73 views

Finding the CFG (Context Free Grammar) of a language

Can we write a CFG (Context Free Grammar) for the set of all non-empty string whose length are multiple of 3 on the alphabet $ \Sigma = \{A,R,G,C\} $
1
vote
1answer
44 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 ...
0
votes
2answers
68 views

Pushdown Automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...