编程介的小学生 2017-09-19 05:46 采纳率: 20.3%
浏览 702
已采纳

L-system

Description

A D0L (Deterministic Lindenmayer system without interaction) system consists of a finite set SIGMA of symbols (the alphabet), a finite set P of productions and a starting string w. The productions in P are of the form x -> u, where x in SIGMA and u in SIGMA+ (u is called the right side of the production), SIGMA+ is the set of all strings of symbols from SIGMA excluding the empty string. Such productions represent the transformation of the symbol x into the string u. For each symbol x in SIGMA , P contains exactly one production of the form x -> u. Direct derivation from string u1 to u2 consists of replacing each occurrence of the symbol x in SIGMA in u1 by the string on the right side of the production for that symbol. The language of the D0L system consists of all strings which can be derived from the starting string w by a sequence of the direct derivations.
Suppose that the alphabet consists of two symbols a and b. So the set of productions includes two productions of the form a -> u, b -> v, where u and v in {a,b}+, and the starting string w in {a,b}+. Can you answer whether there exists a string in the language of the D0L system of the form xzy for a given string z? (x and y are some strings from SIGMA*, SIGMA* is the set of all strings of symbols from SIGMA, including the empty string.). Certainly you can. Write the program which will solve this problem.
Input

The input of the program consists of several blocks of lines. Each block includes four lines. There are no empty lines between any successive two blocks. The first line of a block contains the right side of the production for the symbol a. The second one contains the right side of the production for the symbol b and the third one contains the starting string and the fourth line the given string z. The right sides of the productions, the given string z and the starting string are at most 15 characters long.
Output

For each block in the input there is one line in the output containing YES or NO according to the solution of the given problem.
Sample Input

aa
bb
ab
aaabb
a
b
ab
ba
Sample Output

YES
NO

  • 写回答

1条回答 默认 最新

  • devmiao 2017-10-04 01:22
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 输出区间内所有的完数的个数。 要简单点的程序
  • ¥15 asp.core 权限控制怎么做,需要控制到每个方法
  • ¥20 while循环中OLED显示中断中的数据不正确
  • ¥15 这个视频里的stm32f4代码是怎么写的
  • ¥15 串口发送数据和接收数据
  • ¥15 JNA调用DLL报堆栈溢出错误(0xC00000FD)
  • ¥15 请教SGeMs软件的使用
  • ¥15 自己用vb.net编写了一个dll文件,如何只给授权的用户使用这个dll文件进行打包编译,未授权用户不能进行打包编译操作?
  • ¥50 深度学习运行代码直接中断
  • ¥20 需要完整的共散射点成像代码