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

learn more… | top users | synonyms

0
votes
1answer
163 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
1
vote
1answer
51 views

NFA from regular expression

I'm trying to make an NFA from the following regular expression. I'm not sure about the edges between nodes $q2$ and $q4$, maybe someone can point out where everything went wrong.
0
votes
1answer
29 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...
1
vote
1answer
23 views

Regular expression for a language

I made a regular expression to match this language but I'm not sure it's right. Perhaps someone can show me where it deviates. The language: $L = {a^{n} c b^{m} (cc)^{p} : n \geq 1, m \leq 1, p\geq ...
0
votes
2answers
69 views

Constructing regular grammar

I'm trying to make a regular grammar for this language: $$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$ Where the alphabet is $ \Sigma = \{a,b,c\}$ It seemed like right-linear. This may be ...
3
votes
2answers
136 views

context free grammar problem

$L$ is the context free grammar over $\{a, b\}$ $S \rightarrow aSb \; | \;bR \; |\;Ra$ $R \rightarrow bR \;|\;aR\;|\;\epsilon$ Briefly describe this CFG with English sentences and prove your ...
0
votes
2answers
53 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
1
vote
2answers
124 views

interpreting language for finite state machine

Can someone explain to me what this means in clear english and maybe give me a hint for how to make a NDFSM (non-deterministic finite state machine) that accepts this language? I understand that the 3 ...
0
votes
2answers
56 views

$2^E$ where $E$ is a set

I'm studing the definition of automaton $G=(X, E, f, \Gamma, x_o, X_m)$ where $X$ is the set of states and $E$ is the set of events. My sources report that $\Gamma:X \rightarrow 2^E$ is the indicator ...
1
vote
1answer
94 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 ...
0
votes
2answers
330 views

Finite automata for any even number of a's followed by any even number of b's

I'm new to formal languages. I'm stuck with the following question. Any help is appreciated. Find finite automata for $$L = \{a^i b^j \mid i, j\text{ are even, }j\ge0\}$$ Thank you
4
votes
2answers
119 views

Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and $s$ has length $i$}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
0
votes
1answer
308 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
2answers
325 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
2answers
79 views

The Relation of Cellular Automata to Languages

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language? In probabilistic cellular automata, are ...
0
votes
1answer
53 views

Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

In the Book Infinite Words (homepage) it is proofed that: If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1) $X$ is closed (2) $X$ is recognized by a ...
0
votes
1answer
116 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
1
vote
2answers
273 views

Converting from NFA to a regular expression.

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows $$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) ...
1
vote
1answer
59 views

Is there an (explicit?) bijection from the set of all automatons to the set of all regular expressions that conserves the recongnised language

Let $\Sigma$ be an alphabet, $R$ be the set of regular expressions on $\Sigma$ (that is, trees with leave's values in $\left\{\varepsilon\right\}\cup \Sigma$ and three types of interior nodes, one ...
0
votes
2answers
537 views

To design a Finite State machine

Design a FSM for a binary number in which the input is valid if no. of 0's divisible by 5 and no. of 1's divisible by 3
1
vote
2answers
93 views

Finite automata and languages question

I have attempted these few simple questions, can someone let me know if this is correct please? If not please provide the answer as I learn better that way and if possible explain. i) FA1 Start = ...
2
votes
0answers
51 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
49 views

Quality of Reduction of finite automata

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a ...
1
vote
1answer
218 views

Best book for automata theory and compiler design?

I am currently pursuing my M.Tech in Digital Image Processing, I want to take admission in PhD program using subjects either Formal Language and Automata Theory or Compiler Design, Can anyone please ...
1
vote
0answers
19 views

Given two minimal FSMs with one accepting a subset of the other, must a simulation exist?

As part of an example, Abstract and Concrete Categories, section 3.35, claims: For every two minimal [by number of states] $\Sigma$-acceptors $A$ and $A'$, there exists at most one simulation $A ...
0
votes
0answers
31 views

how to create a automata for a discrete Duration Calculus

can someone explain, how to create a time-automatathat accept the language? $$ \mathcal{L}(\diamond(l=1) ) $$ I don't know how to realize the diamond-operator //UPDATE the lozenge is the diamond ...
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 ...
0
votes
1answer
154 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
1
vote
2answers
159 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 ...
2
votes
2answers
51 views

Regular composition of non-regular language

I've got the following problem: Let's take language $L$. Is it posible that $L$ is not regular itself, but it's composition $L\cdot L$ becomes regular? I suspect that's correct, yet I ...
1
vote
1answer
637 views

Proof that equal-length-concatenation is a context-free language?

If A and B are languages, define A⋄B={xy | x ∈ A and y ∈ B and |x|=|y|}. For example, if A = {00, 101, 111} and B= {1, 11, 00110}, we would have A⋄B={0011}. Show that if A and B are regular, ...
0
votes
2answers
66 views

Algorithm for a regular expression

This was a question for an exam that I received 0 points on, I'd like to get some input on what the correct answer should have been. Imagine that you are asked to write an algorithm P that takes a ...
2
votes
3answers
764 views

Find push down automata and context free grammar

I have the following language: $$ L = \{a^nb^{2n+1} \mid n \ge 0\} $$ I must find the push down automaton and a context free grammar for the language. For the push down I have no idea how to ...
1
vote
1answer
94 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? ...
0
votes
2answers
129 views

regular expression

I would like to write the regular expression for the set of all binary strings where there are no three consecutive 0's. The following strings are part of the language: ...
0
votes
2answers
151 views

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular. It seems to use one Lemma: Pumping Lemma.
3
votes
2answers
169 views

Automata: 1=2, 2= 26, 3=1054, 4=5768, 5 =139314069504, 6 = ???

I am in my own Automaton (finite-state deterministic automata) research, so i have four sets of automata. 2 states automata, 3 states, 4 states and 5 states. Input alphabet $\{0,1\}$ so... the ...
0
votes
1answer
43 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
2
votes
2answers
129 views

An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?

One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
1
vote
1answer
115 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
1answer
156 views

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $? I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
0
votes
0answers
291 views

Turing Machine question, this is NOT HW

I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
-1
votes
1answer
177 views

Decidability/Undecidability Question

Could someone please help me with this question? I'm really having a hard time understanding reductions and decidability. Prove that the language $$L = \{\langle M,N \rangle \mid M,N\text{ are Turing ...
2
votes
1answer
124 views

DFA worst case states

Suppose an NFA which accepts language of the form L(N) = {w| w has 1 in n$^t$$^h$ from last symbol.} Then the corresponding DFA would have 2$^n$ states(worst case of subset construction). If we are to ...
1
vote
1answer
384 views

Proving Language accepted by DFA

I am stuck with a problem, as my proving skills aren't good(trying to improve). Prob: Given a State Table of DFA, decribe what language is accepted, and prove by induction it accepts that language, ...
0
votes
0answers
78 views

Pumping Lemma length, $K$ for context-free language

Please help me understand, and if possible, tips, to determine a pumping length $K$. Suppose I have the example : Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
0
votes
1answer
126 views

Decidability of a Turing machine always halting in at most ten steps

I've exam comping up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove your ...
2
votes
1answer
290 views

Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]

How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
2
votes
1answer
64 views

Constructing PDA with either one state or two states

If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
0
votes
1answer
280 views

Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3.

I have exam coming up and I need help with this: Describe a Turing Machine that accepts the language of all non-negative decimal integers that are multiples of 3 Thank you :)