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

learn more… | top users | synonyms

0
votes
0answers
9 views

What are the classes in A.N. Maslov hierarchy of indexed languages corresponding to Chomsky Hierachy?

As we know,that classes in A.N. Maslov hierarchy of indexed languages of level 2 is in sensitive languages of Chomsky hierarchy. What are the classes in A.N. Maslov hierarchy of indexed languages ...
0
votes
0answers
15 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
0
votes
0answers
15 views

finding right quotient of languages

Can someone enumerate in detail, steps to find right quotient of languages ie L1/L2. Using an examle will be great. Having a hard time to understand the same.
3
votes
1answer
66 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
29 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?
1
vote
1answer
23 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
1answer
65 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
33 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}$$
0
votes
0answers
12 views

Struggling to prove Markov chain property / State machine property - I can see what I need to do just can't write it

First notation, I have created the shorthand: $$P_x(A)=\mathbb{P}(A|X_0=x)$$ just to save time. I wish to prove "Lemma 1.3" which states the following: If $0<\alpha\le P_x(T_y\le k) \forall x\in ...
2
votes
1answer
24 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 ...
3
votes
2answers
27 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
59 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
58 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
0answers
24 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
34 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
1answer
22 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
52 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 ...
1
vote
1answer
14 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
89 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
28 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
31 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
0answers
22 views

CFG Convertion to GNF

I have a very simple CFG that I am trying to convert into GNF. The CFG is: S -> aSbS S -> epsilon I looked at the CFG and I think I can just do the ...
0
votes
1answer
21 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
38 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
23 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
26 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
50 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
34 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
41 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
31 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
35 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
29 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
35 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
65 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
68 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
46 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
48 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
35 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
52 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 ...
1
vote
2answers
26 views

FSM to be regular with atleast two 0's and at most two 1's

Is it possible to construct a FSM to prove that the set $X$ is regular, where $$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$
0
votes
1answer
29 views

using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
1
vote
4answers
150 views

Prove this language is not regular [closed]

How do I prove that this language = {1^k | k is a perfect square} is not regular by showing that no DFA can accept the language?
1
vote
1answer
39 views

Can someone explain me the proof?

I don't really understand the proof and I don't understand why it is M2 that "leads" to a reject state instead of M1.
1
vote
1answer
40 views

Can someone explain to me how this is a proof?

I honestly don't understand how this proves anything.
1
vote
2answers
34 views

Closed regular languages

Are regular languages closed under the following construction? $f(L) = \{w \mid w \in L$ and for all prefixes $x$ of $w$ it holds that $x \notin L$ $\}$
0
votes
1answer
50 views

How to convert this NFA to DFA?

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/nfa-dfa1.jpg What are the steps for convert this NFA to DFA??
1
vote
0answers
37 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
0
votes
0answers
30 views

Context-free languages

Is the following language context-free? $\{ w \in \{a,b,c\}^* : (\#_a(w) - \#_b(w)) \cdot \#_c(w) = \#_b(w)$ and all c's are encountered before any a$\}$. $\#_a(w)$ = amount of a's in w Thanks 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
22 views

Subset of regular languages

Assume $L_1$ and $L_2$ two regular languages, and $L_1\subseteq L\subseteq L_2$. Does this imply that $L$ is a regular language? Thanks in advance.